Problema al generar primos en Delphi

[[nlsgarcia]]

XavierAramayo,

Empezado por XavierAramayo

...ingresar un número n y que me mostrase los n primeros números primos...

¡Bienvenido al Club Delphi!

Revisa este código:

Código Delphi [-]
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    ListBox1: TListBox;
    Edit1: TEdit;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

// Genera n números primos ( n <= MaxInt )
function GeneratorNumberPrime(Limit : Integer) : TStringList;
var
   n,i,c : Integer;
   rn : integer;
   NumberPrime : TStringList;
   Prime : Boolean;

begin

   n := 3;
   NumberPrime := TStringList.Create;
   NumberPrime.Add('1');
   NumberPrime.Add('2');
   c := 0;

   While (c <= Limit - 3) do
   begin

      Prime := True;
      rn := Trunc(sqrt(n));

      for i := 2 to rn do
      begin
         if (n mod i) = 0 then
         begin
            Prime := False;
            break;
         end;
      end;

      if Prime then
      begin
         NumberPrime.Add(IntToStr(n));
         Inc(c);
      end;

      Inc(n,2);

   end;

   Result := TStringList.Create;
   Result.Assign(NumberPrime);
   NumberPrime.Free;

end;

// Genera n números primos, por defecto o error se generan 10.
procedure TForm1.Button1Click(Sender: TObject);
var
   Limit : Integer;
begin
   Limit := StrToIntDef(Edit1.Text,10);
   ListBox1.Items.Assign(GeneratorNumberPrime(Limit));
end;

end.

El código anterior genera n números primos dado un número límite de la función generatriz, como se muestra en la siguiente imagen:



El ejemplo esta disponible en el link: http://terawiki.clubdelphi.com/Delph...mber+Prime.rar

Espero sea útil

Nelson.

[[nlsgarcia]]

XavierAramayo,,

Continuación del Msg #2:

Empezado por Wikipedia:

En matemáticas, un número primo es un número natural mayor que 1 que tiene únicamente dos divisores distintos: él mismo y el 1. Los números primos se contraponen así a los compuestos, que son aquellos que tienen algún divisor natural aparte de sí mismos y del 1. El número 1, por convenio, no se considera ni primo ni compuesto.

Tomado de: http://es.wikipedia.org/wiki/N%C3%BAmero_primo

En función de la definición anterior, el código del Msg #2 se redefine a continuación:

Código Delphi [-]
unit Unit1;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    Button1: TButton;
    ListBox1: TListBox;
    Edit1: TEdit;
    Label1: TLabel;
    procedure Button1Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

// Genera n Números Primos ( n <= MaxInt )
function GeneratorNumberPrime(Limit : Integer) : TStringList;
var
   n,i,c : Integer;
   rn : integer;
   NumberPrime : TStringList;
   Prime : Boolean;

begin

   NumberPrime := TStringList.Create;
   c := 0;
   n := 2;

   repeat

      Prime := True;
      rn := Trunc(sqrt(n));

      for i := 2 to rn do
      begin
         if (n mod i) = 0 then
         begin
            Prime := False;
            break;
         end;
      end;

      if Prime then
      begin
         NumberPrime.Add(IntToStr(n));
         Inc(c);
      end;

      Inc(n);

   until (c = Limit);

   Result := TStringList.Create;
   Result.Assign(NumberPrime);
   NumberPrime.Free;

end;

// Genera n números primos, por defecto o error se generan 10.
procedure TForm1.Button1Click(Sender: TObject);
var
   Limit : Integer;
begin
   Limit := StrToIntDef(Edit1.Text,10);
   ListBox1.Items.Assign(GeneratorNumberPrime(Limit));
end;

end.

El código anterior, genera n números primos desde el 2 hasta un máximo definido como parámetro en la función generatriz, como se muestra en la siguiente imagen:



El ejemplo esta disponible en el link: http://terawiki.clubdelphi.com/Delph...me_Numbers.rar

Espero sea útil

Nelson.

[XavierAramayo]

Muchas gracias [nlsgarcia],ya lo consegui,gracias!

[Victor Luis]

Holas...

Muy bueno el codigo de Garcia, solo que esta limitado a busquedas menores, si ponemos n=1.500.000 tardara un poco mas de 6 minutos que seria encontrar primos hasta 25 millones como limite de busqueda y si n=3.001.146 para encontrar numeros primos hasta 50.000.000 tarda mas de 20 minutos y logicamente al ir incrementando esto se demora cada vez mas. Esto sucede basicamente por 2 razones: 1) Evaluan todos los numeros naturales secuencialmente, donde se deberia no evaluar numeros que sean multiplos de 2, 3 y 5 que de hecho no son primos. 2) Evaluas si es multiplo cada numero natural desde 2 hasta la raiz cuadrada del numero en evaluacion, donde al incrementarse el numero tambien se incrementan los calculos y el tiempo se alarga de una manera exponencial 2/4/8/16/...

◘ El metodo PRI-BASE genera una secuencia base de numeros naturales donde el 50-75% son casi directamente primos, de los cuales solo hay que depurar los que no son primos. En un Rango de 1 a 50.000.000 busca y saca numeros primos en 24-27 segundos y sacar primos en un rango de 1.000.000.000 lo hace en menos de 9 minutos donde encuentra en promedio 36.500.000 nuevos numeros primos.
○ Este tiempo reducido no solo es por generar la secuencia base de numeros casi primos, sino esencialmente porque no factoriza ni realiza calculos para saber si es multiplo de numeros primos anteriores al numero ni hasta su raiz cuadrada; simplemente determina una secuencia para depurar de la base de numeros generados, eliminando los no primos y guardando los nuevos numeros primos.
► Lo que deben considerar si desean buscar numeros primos grandes, es el metodo, si evaluan para saber si es multiplo de otros primos, elproceso sera lento por los calculos, llegara un momento en que las variables no podran hacer estos calculos y necesitaran mucho espacio en su disco duro o enlazar tipo red varias computadoras para almacenar todos los numeros primos que saquen pues los necesitan para ver si es multiplo entre estos.

◘ La sugerencia esta dada, para que lo tomen en cuenta, sin desmerecer los metodos que proponen y funcionan bien hasta cierto limite; el consejo es para quienes quieran buscar numeros primos con millones de digitos.

Un saludo cordial a todos y sigan adelante...

[Casimiro Noteví]

¿Y por qué no lo explicas poniendo el código fuente de ejemplo?, así como lo has explicado queda muy "aséptico y vaporoso", pero no vemos nada tangible

[[nlsgarcia]]

Victor Luis,

Empezado por Victor Luis

...el código de Garcia...esta limitado a búsquedas menores...al incrementarse el número también se incrementan los cálculos y el tiempo se alarga de una manera exponencial...Lo que deben considerar si desean buscar números primos grandes, es el método...

...El metodo PRI-BASE genera una secuencia base de números naturales donde el 50-75% son casi directamente primos, de los cuales solo hay que depurar los que no son primos...

Gracias por tus comentarios

En internet conseguí esta referencia al método que sugieres PRI-BASE, al parecer la referencia es de tu autoría y en ella se da a entender que es un procedimiento nuevo que tu desarrollastes y que esperas poder patentar, Pregunto: ¿Es correcto?.

Sería muy interesante conocer más detalles de este método y si es posible ver alguna implementación del mismo, el tema de los números primos es muy importante en matemáticas y su aplicación práctica en métodos de cifrado en informática.

Nelson.

[Victor Luis]

Holas Nelson...

Respecto a lo de patentar, busque me dieran sugerencias mas claras de las que encontre y esto porque he ido revisando los metodos publicados en internet desde la criba de Eratostenes hasta los metodos y formulas matematicas que usan para determinar si un numero es o no primo.

◘ Con referencia al metodo PRI-BASE, un hermano mio me dijo una vez que los Incas de Machu-Pichu tenian un metodo con el que obtenian los numeros primos facilmente. Mi pensamiento fue que si ellos no contaban con computadoras ni formulas complejas, como lo podian hacer o tal afirmacion no era cierta.
Antes de saber de la criba de Eratostenes, encontre un metodo para sacar los supuestos primos que se ordenan en columnas, claro que hay varios por depurar. Con ese metodo reduje muchisimo el tiempo de busqueda, por ejemplo hasta el limite de 1 millon encontrar los primos que hay dividiendo y viendo si es multiplo de primos anteriores hasta la raiz cuadrada, tardaba 42 segundos. Aplicando el metodo que mencione, sacaba estos supuestos primos y solo debia depurarlos, sin analizar los demas y el tiempo se redujo a 16 segundos, optimizando un poco lo hacia entre 2-3 segundos.
No se si este metodo lo hicieron ya pero no encontre referencia alguna, de los codigos que publican la mayoria utiliza varios If Then y por referencia se que esto retarda el tiempo de proceso. En este metodo solo usaba 1 If Then que era para finalizar la busqueda.

◘ El Metodo PRI-BASE nace a razon de mejorar el anterior que mencione, donde encontre un modo de obtener los supuestos primos pero mas depurados, por eso los llamo casi primos directos, pues hay pocos por depurar y logicamente el tiempo de proceso se redujo a menos de 1 segundo para un limite de 1 millon.
Dejarlo asi llegaria a lo mismo que los otros metodos, donde uno debe tener a disposicion todos los primos encontrados para factorizar o comprobar que son divisibles. Volviendo a que los Incas no tenian computadoras, encontre la manera directa de depurar los no primos, sin recurrir a todos los primos. Cuando le mando a buscar primos en un rango de 1.000.000.000 el programa solo saca unos datos de algunos primos, entre 50 y 250 a los que llamo activados, ya que luego no necesito volver a leerlos. Esto permite no contar con una super computadora de muchisima memoria en disco duro, solo necesito un archivo de 348 MB donde estan 36 millones de primos para realizar Busquedas con rangos de hasta 1 Billon.
► Encontre una pagina donde por factorizacion evalua si el numero que uno pone es primo o no, donde todos los que fui obteniendo son primos. Baje algunos archivos de listas de primos ya verificados y coinciden con los que voy obteniendo, no conforme con esto hice un procedimiento con el metodo clasico de ver si es divisible entre primos anteriores, los compare y todos coinciden en secuencia y cantidad. Esto me da la seguridad de que el metodo funciona adecuadamente.

◘ Para complementar tu consulta sobre el Metodo PRI-BASE es que el tiempo de busqueda es casi constante y en lugar de alargarse el tiempo de proceso tiende a disminuir, ya que en cada rango buscado encuentra menor cantidad de numeros primos.
Mi Objetivo es determinar cuando ocurre este descenso, ya que hasta ahora no es constante, en ciertos rango aumenta, luego se mantiene y despues disminuye la cantidad de nuevos primos, repitiendose esto pero en forma desordenada.
Otro objetivo es obtener primos gemelos y ver su frecuencia de aparicion, para lo cual el metodo me permite identificar precisamente las posiciones de la secuencia donde estan, si ambos son primos entonces son primos gemelos.

Bueno, esos son algunos detalles del metodo y respecto a publicar el codigo, no lo veo prudente, como dije no he encontrado un metodo similar ... si alguien sabe de uno se lo agradeceria que me lo haga saber.
Con la explicacion dada sera facil que lleguen al metodo, para lo cual deben quitar se su cabeza la factorizacion y la divisibilidad de un numero entre otros primos para saber si este es o no primo. Aunque parezca ilogico, es como funciona el metodo... simple y directo.


Espero haber respondido a la consulta de Nelson... gracias