23/09/2019, 09:03:01 am *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.
¿Perdiste tu email de activación?

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: ¡Atención! Hay que poner la matemática con LaTeX, y se hace así (clic aquí):
 
 
Páginas: [1]   Ir Abajo
  Imprimir  
Autor Tema: Algoritmo de Tamiz "PRI-BASE" para Buscar Números Primos  (Leído 1172 veces)
0 Usuarios y 1 Visitante están viendo este tema.
Víctor Luis
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Bolivia Bolivia

Mensajes: 1.145


Ver Perfil
« : 04/07/2014, 11:50:04 am »

Un saludo cordial a todos los integrantes y organizadores de este excelente espacio web.

Inicio este hilo para presentar el algoritmo de tamiz PRI-BASE que busca y genera numeros primos, en base a los "Primos Origen" y las relaciones especificas entre estos.
Toda idea constructiva es bienvenida, para ir aprendiendo de nuestros errores y cultivar nuestra capacidad y conocimiento.

* Pseudocodigo de PRI-BASE en DELPHI 7:

Código:
VARIABLES de INICIO:
FM..... Factor Multiplo de generacion
PO..... Numero de Primos Origen


Procedure TUFCON1.BPRIM3Click(Sender: TObject);
var
   VP: array[0..1,0..20] of extended;
   VN: array[0..50000000,0..10] of byte;
   q,n,s: integer;
   i,ctt,cct,np,po,fm,pv1,pv2,nv1,nv2: longint;
   np1: extended;
   
Begin
CargaVDS;
{- Carga en el array VDS los Primos Origen
   y los Primos Relacionados}

np1:=strtofloat(ET1.Text); //Limite BUSQUEDA
ctt:=trunc(np1/fm);

For n:=1 To po Do
begin
vp[0,n]:=vds[0,n];
vp[1,n]:=(ctt*fm)+vds[0,n];
end;
np:=0;
cct:= trunc(exp((1/2) * ln(vp[1,po])));

//.. PRIMERA DEPURACION
For q:=1 To po Do
begin
For n:=1 To po Do
begin
pv1:=vds[0,n]; //Primo Origen Base
pv2:=vds[q,n]; //Primo Origen Relacionado
nv1:=trunc(((pv1*pv2)-vds[0,q])/fm);
While (pv1<=cct) do  //Limite Ultimo Primo Divisor
Begin
nv2:=nv1;
While (nv2<=ctt) do  //Limite Ultimo Multiplo
begin
vn[nv2,q]:=1; //Marca Numero Base como Multiplo
nv2:=nv2+pv1;
end;
pv1:=pv1+fm;
nv1:=nv1+pv2;
end;
end;
end; //Fin de Depuracion

//.. Cuenta ó Exporta Numeros Primos validos
For i:=1 To ctt Do
begin
For q:=1 To po Do
begin
If vn[i,q]=0 then np:=np+1;
end;
end;

Showmessage('N° de PRIMOS: '+floattostrF(np,ffNumber,15,0));

end;


METODOLOGIA.
• Dado un límite hasta donde buscar numeros primos, determinamos en la variable "ctt" la cantidad de filas a depurar del array VN, que es una matriz, donde cada columna corresponde a los elementos de un Grupo Origen.
• Sabiendo el limite calculado en "ctt" cargamos en el array VP, en la Fila[0, n] los numeros primos origen y en la Fila[1, n] los ultimos numeros base correspondientes al limite de busqueda, con el cual calculamos en la variable "cct" cuantos primos base utilizar para marcar y depurar sus multiplos que son primos.
• En la etapa de Depuracion utilizamos un bucle para controlar los grupos origen donde se realizará la depuracion.
• Luego utilizamos otro bucle para los primos relacionados, que nos indican desde donde iniciar la depuracion de multiplos correspondientes a los elementos del grupo relacionado, mediante los bucles While que se continuan, donde los multiplos se marcan poniendo el valor =1 en la matriz VN.
• Al finalizar la depuracion, se cuentan y/o eportan como numeros primos todos los campos de la matriz que sean =0 lo que nos indica que no son multiplos de ninguno y por tanto son primos validos.

RENDIMIENTO.
○ Segun la capacidad del equipo que permita dimensionar el array VN, se realizará un ciclo de depuracion o varios hasta llegar al limite indicado.
Por ejemplo, dimensionando:
   VN: array[0..50000000,0..10] of byte;
se podrá buscar numeros primos hasta un limite de 1.000.000.000 con un solo ciclo de depuracion.

○ La cantidad de numeros primos existentes es determinada con precisión, para exportarlos, multiplicamos el numero de fila del campo no depurado por "fm" el factor multiplo de generacion y al producto sumamos el primo origen correspondiente a la columna del campo no depurado, obteniendo el valor del numero primo.
→Para limites altos como el indicado, exportar los numeros primos a un ListBox u otro objeto, consumirá recursos de la memoria operativa, haciendo lento el proceso.
En este caso, lo mejor seria abrir un fichero tipo texto y exportar ahi los numeros primos encontrados.

* En base a la metodologia expuesta, se pueden realizar mejoras para reducir las lineas de codigo y buscar numeros primos para limites mas grandes, segun la capacidad de las variables.

Saludos a todos...
En línea
Páginas: [1]   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!