11 millones de números primos

[ixMike]

"11 millones de números primos" o "sobre la evolución personal en la programación".

Muy buenas.

Pasaba por aquí, y no he podido evitar dar a conocer un pequeño proyecto sin importancia al que me he estado dedicando últimamente. Bueno, tendría que contaros la historia, ¡y es que a 11 millones de números primos no se llega así como así! Y menos con los pocos conocimientos de programación con los que empecé.

Procedure ContarHistoria(AQuien: TDestinatario);
begin
If AQuien=GenteDelClubDelphi then
begin
PedirAlgo('¡Camarero, una ronda y un platico de jamón y queso!');
SoltarElRollo('
En fin, "once upon a time in my home", cuando llevaba poco tiempo en el fascinante mundo de la programación en Delphi (bueno, la programación en general) se me ocurrió hacer un simple programa que pudiera descomponer un número en sus factores primos. Pero entonces pensé «Necesitaré una lista de números primos», así que al programa tuve que añadirle un generador de números primos. Le indicabas un rango de números (del 2 al 1000, por ejemplo), e iba comprobando si todos los números comprendidos en ese rango eran primos. Observé que me salió bastante bien: el rango 2-1000 me lo sacaba en muy pocos segundos. Los números se almacenaban en un TMemo, y yo me encargaba de añadirlos a un archivo llamado "primos.txt". Después, cada vez que abría el programa, "primos.txt" se cargaba en otro TMemo (para hacerlo bonito, más que nada), y esa era la lista de primos a la que accedía el descomponedor en factores primos.

Todo iba "bien", hasta que, claro, no tenía suficientes números primos, a la hora de calcular descomposiciones de números muy grandes. Así que tuve que agrandar la lista de números primos, pero a partir del 100.000, el cálculo empezaba a resultar demasiado lento. Y ahí fue donde realicé las primeras optimizaciones al código: dejé de comprobar los números pares (pues obviamente no son primos), a la hora de comprobarlos tampoco probaba con divisores pares (pues si el número a comprobar no era par pues perdía el tiempo con esos cálculos). Además descubrí el "Memo.Lines.BeginUpdate". ¡Violá! De repente tenía ante mí un código que me pareció tremendamente rápido. Empecé a calcular primos hasta que, cuando iba por el rango 2.000.000-2.100.000 (me parece recordar) la cosa se volvía otra vez lenta: tardaba alrededor de un minuto en calcularlo.

A partir de ahí la cosa quedó un poco abandonada, si eso de vez en cuando hacía crecer el rango 100.000 más, sacando unos pocos miles de números primos.

Pero hace poco, anteayer concretamente, lo vi y me dije «¿Y si aplico todo lo que he aprendido y realizado estos años para optimizar el código al máximo?». Y así hice. Primero pasé del TStringList al TIntegers, un objeto que creé hace tiempo con otra necesidad, y que se puede deducir qué es y cómo funciona (y si no, pues lo digo, es como TStringList, pero en vez de Strings almacena Integers). Además me dejé de interfaz gráfica (porque llevo tres días sin mouse y el IDE de Delphi sin mouse...). Así que creaba un .dpr vacío, y empezaba el programa de cero. La entrada y salida de datos la hacía con parámetros (que son fáciles de utilizar con la consola o teniendo instalado FileMenuTools).

Lo primero fue crear dos programas, el ttn.exe y el ntt.exe, que transforman un archivo de texto con números listados en un archivo con números listados (que es el que puede cargar y guarda el TIntegers). Después optimicé un poco más el código para comprobar si un número es primo o no (antes comprobaba si era divisible por todos los números impares hasta su mitad, pero matemáticamente sólo es necesaria esta comprobación hasta llegar a su raíz cuadrada truncada). Además desarrollé otro método (que con el TStringList resultaba lentísimo), y es comprobar que el número no es divisible por ningún número primo menor que su raíz cuadrada truncada.

Pero lo de crear un programa que creara primos en un rango ya no me era suficiente, y realicé otro que aumenta el rango de los primos ya calculados. Por ejemplo, ahora que ya había calculado primos del 1 al 3.500.000, pues con sólo decirle que aumentara el rango en 500.000, ya tenía los primos del 1 al 4.000.000, pero ¡ya!, porque no tardó casi nada en realizar el cálculo. Así que fui probando (esto ya ayer por la tarde) y... en unos pocos minutos... ¡ya tenía 11 millones y pico de números primos! Los que van del 1 al 200.000.000.
');
end;
end;

Si cuando empecé con la idea de descomponer un número en sus factores primos alguien me hubiese dicho que en un par de años (o tres) habría realizado un programa que va por comandos, que utiliza un objeto tan potente como TStringList pero que funciona con Integers y que está hecho por mí, y que los primeros 11 millones de números primos se calcularían en unos 10 minutos, no sé cómo habría reaccionado. Supongo que no me lo habría creído. O habría pensado que habría necesitado miles de líneas de código, ¡cuando sólo tiene unas 250!. Y eso que me dedico a la programación por afición (bueno, ahora en la universidad doy C en clase de informática).

¡Ah! Casi se me olvida. Subo el código de los programas, con una breve explicación de su funcionamiento, y una lista de los primeros números primos (los que puedo decir de cabeza) en formato lista de texto y en formato lista numérica. ¡A ver si alguien se anima y lo optimiza un poco más!.

Saludos a todos (y espero no haberos aburrido con la historia).

[jhonny]

Pues muy interesante tu relato, , lo que mas me llama la atención es tu perseverancia con dicho proyecto.

[[seoane]]

Bonito entretenimiento, yo tambien me apunto

Con esto calculo los 15.000.000 primeros primos en 20 minutos

Es una aplicacion de consola:

Código Delphi [-]
program Primos;

{$APPTYPE CONSOLE}

uses
  Windows, SysUtils;

const
  Limit = 15000000; // Cantidad de numeros primos a generar

procedure WriteTable(T: PInteger);
begin
  Writeln(1);
  while T^<>0 do
  begin
    Writeln(T^);
    inc(T);
  end;
end;

procedure SaveTable(T: PInteger; Filename: String);
var
  F: Text;
begin
  AssignFile(F, Filename);
  {$I-}
    Rewrite(F);
  {$I+}
  if IOResult = 0 then
  begin
    Writeln(F,1);
    while T^<>0 do
    begin
      Writeln(F,T^);
      inc(T);
    end;
    CloseFile(F);
  end;
end;

function Test(N: Integer; T: PInteger): Boolean;
var
  i: Integer;
begin
  Result:= TRUE;
  i:= Trunc(Sqrt(N));
  while (T^<>0) and (T^<=i) do
    if N mod T^ = 0 then
    begin
      Result:= FALSE;
      break;
    end else
      inc(T);
end;

procedure Generate(T: PInteger);
var
  i,j: Integer;
  P: PInteger;
begin
  P:= T;
  P^:= 2;
  inc(P);
  j:= 3;
  i:= 2;
  while i <= Limit do
  begin
    if Test(j,T) then
    begin
      // Esto ralentiza un poco, pero sino el programa es muy aburrido, jejeje
      Write(Format('Generados: %d Ultimo: %d %s',[i,j,#13]));
      P^:= j;
      inc(P);
      inc(i);
    end;
    inc(j,2);
  end;
end;

var
  Table: PInteger;
  Ticks: Cardinal;

begin
  GetMem(Table,(Limit + 1) * Sizeof(Integer));
  try
    FillChar(Table^,(Limit + 1) * Sizeof(Integer),#0);
    Writeln('Generando numeros primos ...');
    Ticks:= GetTickCount;
    Generate(Table);
    Ticks:= GetTickCount - Ticks;
    Writeln;
    Writeln;
    Writeln(Format('Se han empleado %d ms',[Ticks]));
    //WriteTable(Table);
    SaveTable(Table,ChangeFileExt(ParamStr(0),'.txt'));
  finally
    FreeMem(Table);
  end;
end.

El programa anterior muestra algo como esto:

Generando numeros primos ...
Generados: 15000000 Ultimo: 275604541

Se han empleado 1217984 ms

Y además crea un fichero de texto con todos los números primos generados. (Ojo! es un archivo de 150 MB)

Alguno se anima a mejorar el tiempo

[Robert01]

¿Mejorar el tiempo usando otro algoritmo?

[[seoane]]

Empezado por Robert01

¿Mejorar el tiempo usando otro algoritmo?

Pues como tu quieras, usando el mismo algoritmo u otro mejor. El caso es perder el tiempo

[[egostar]]

Empezado por seoane

Pues como tu quieras, usando el mismo algoritmo u otro mejor. El caso es perder el tiempo

Hey, amigo Domingo, solo porque no te gustan las "ventanas" si no hacia un upgrade de tu aplicación de consola

Salud OS

[[seoane]]

Empezado por egostar

Hey, amigo Domingo, solo porque no te gustan las "ventanas" si no hacia un upgrade de tu aplicación de consola

Caramba amigo Eliseo, ya piensas como Bill Gates. Llegaras lejos

[Robert01]

Invertí algo más de 18 minutos, la salida es como lo habías dicho un monstruoso archivo de cerca de 150 mb.

Siempre me pregunté si los números primos servían para algo..., algo útil quiero decir.


Saludos

[[seoane]]

Empezado por Robert01

Siempre me pregunté si los números primos servían para algo..., algo útil quiero decir.

Pues se usan en criptografía, precisamente porque no se pueden descomponer en factores. Romper un cifrado no deja de ser un problema matemático, y al usar números primos la resolución del problema se complica muchísimo, y cuanto mas grandes mejor.

[Robert01]

Seoane: tu código compilado en FreePascal bajo windows fue 5 min y medio más rápido que el compilado con delphi.

Me gustaría probar que pasa compilandolo con Freepascal bajo linux pero hay partes del código que no se como modificar para que compile sin errores

Saludos

[[seoane]]

Empezado por Robert01

Me gustaría probar que pasa compilandolo con Freepascal bajo linux pero hay partes del código que no se como modificar para que compile sin errores

Pues para linux solo hay que quitar la función GetTickCount que es propia de Windows.

(primos.pas)

Código Delphi [-]
program Primos;

{$APPTYPE CONSOLE}

uses
  SysUtils;

const
  Limit = 15000000; // Cantidad de numeros primos a generar

procedure WriteTable(T: PInteger);
begin
  Writeln(1);
  while T^<>0 do
  begin
    Writeln(T^);
    inc(T);
  end;
end;

procedure SaveTable(T: PInteger; Filename: String);
var
  F: Text;
begin
  AssignFile(F, Filename);
  {$I-}
    Rewrite(F);
  {$I+}
  if IOResult = 0 then
  begin
    Writeln(F,1);
    while T^<>0 do
    begin
      Writeln(F,T^);
      inc(T);
    end;
    CloseFile(F);
  end;
end;

function Test(N: Integer; T: PInteger): Boolean;
var
  i: Integer;
begin
  Result:= TRUE;
  i:= Trunc(Sqrt(N));
  while (T^<>0) and (T^<=i) do
    if N mod T^ = 0 then
    begin
      Result:= FALSE;
      break;
    end else
      inc(T);
end;

procedure Generate(T: PInteger);
var
  i,j: Integer;
  P: PInteger;
begin
  P:= T;
  P^:= 2;
  inc(P);
  j:= 3;
  i:= 2;
  while i <= Limit do
  begin
    if Test(j,T) then
    begin
      // Esto ralentiza un poco, pero sino el programa es muy aburrido, jejeje
      Write(Format('Generados: %d Ultimo: %d %s',[i,j,#13]));
      P^:= j;
      inc(P);
      inc(i);
    end;
    inc(j,2);
  end;
end;

var
  Table: PInteger;
  Marca: TDateTime;

begin
  GetMem(Table,(Limit + 1) * Sizeof(Integer));
  try
    FillChar(Table^,(Limit + 1) * Sizeof(Integer),#0);
    Writeln('Generando numeros primos ...');
    Marca:= Now;
    Generate(Table);
    Writeln;
    Writeln;
    Writeln('Se han empleado un tiempo de: ' + FormatDateTime('hh:nn:ss',Now-Marca));
    //WriteTable(Table);
    SaveTable(Table,ChangeFileExt(ParamStr(0),'.txt'));
  finally
    FreeMem(Table);
  end;
end.

[Robert01]

Tube que cambiar una cosa debido aun error:

{$apptype console} por {$mode objfpc}

En linux tardó 00:23:06 y el archivo de salida fue de 7.3 mb
En windows usando el mismo código 00:15:39 y el archivo de salida 136 mb.

No puedo creer que el código en linux ande más lento.

Un saludo y gracias

[ixMike]

Empezado por Robert01

En linux tardó 00:23:06 y el archivo de salida fue de 7.3 mb
...No puedo creer que el código en linux ande más lento.

Bueno, dejando las comparaciones de velocidad, ¿cómo es que te ocupó tan poco el archivo? 15 millones de números, a 4bytes cada uno... haz la cuenta, la cifra ronda los 60 MB. Igual ahí está el problema, cambiaste algo de más, y el resultado es incorrecto y, por lo tanto, tarda más (debido a un error).

Revísalo, anda.


Saludos

[ixMike]

Empezado por seoane

Pues se usan en criptografía, precisamente porque no se pueden descomponer en factores.

Bueno, sí, por ahí van los tiros de ahora. Pero también se usan en la compresión de archivos (sacando factor común...). Además, si por casualidad lee esto Wonni (vamos, pásate por aquí, no podrás estar alejado de la programación mucho más) podrá atestiguar cómo me gusta la compresión de archivos (no me empeñé una vez en meter un CD de audio de 210 MB (24 min) en un floppy, ¡y lo conseguí!).


Saludos.

[Victor Luis]

Holas...

El relato es interesante; pero el metodo que aplicas para buscar numeros primos comprobando si es divisible un numero entre numeros primos anteriores incluso hasta la raiz cuadrada de este sera exageradamente lento cuando busques mas alla de 1.000.000.000 ni que decir cuandopases del Billon.
El metodo que uso es PRI-BASE me genera una serie de numeros casi primos directos de los cuales se depuran algunos, el proceso para buscar 10.000.000.000 tarda unos 00:21:37 (21 minutos) de los cuales 3-4 min son de la busqueda en si y el resto es lo que se demora en archivarlos, ya que con este rango encuentra mas de 36.000.000 de numeros primos.

Otro detalle es que el tiempo de busqueda y archivo va disminuyendo al ir avanzando y encontrando primos mas grandes; en cambio con el metodo de factorizacion cada vez tendra que hacer calculos mas largos y complejos, lo que hara mas lento el proceso.

Este metodo es totalmente arbitrario a la logica que nos enseñaron para determinar numeros primos, no necesita tener todos los primos sacados para seguir avanzando en la busqueda,para lo que se necesitarian varias computadoras, con una basta, claro con disco duro de 1 Tera.

Para finalizar te diria que hay muchas maneras de encontrar numeros primos y son simples... piensa y analiza... Suerte


Victor Luis

[Casimiro Notevi]

Empezado por Victor Luis

Victor Luis

Bienvenido a clubdelphi, ¿ya leiste nuestra guía de estilo?, gracias por tu colaboración