11 millones de números primos

[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 Noteví]

Empezado por Victor Luis

Victor Luis

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