11 millones de números primos

[[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

[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.