Problema al generar primos en Delphi

[Casimiro Noteví]

Empezado por nlsgarcia

En el mundo de la ciencia y a nivel profesional se requiere poder demostrar el trabajo realizado y que este pueda ser verificable y repetible por otras personas para comprobar su veracidad y efectividad. Las dudas expresadas en este foro son ciertamente válidas y justificables en todo sentido y honestamente considero poco probable una reacción diferente en otro foro de programación o matemáticas.
Si esperas poder presentar tu trabajo a nivel académico debes tener una fuerte base matemática y en computación, haber revisado los métodos publicados sobre este tema, indicar claramente en que consiste tu algoritmo, cuales son sus ventajas sobre los métodos anteriores y ser capaz de demostrar todo lo sustentado en tus afirmaciones, el mundo académico es ciertamente muy exigente en este sentido.
Te sugiero considerar todo lo comentado en este hilo y nuevamente mucha suerte en tu proyecto
Espero sea útil
Nelson.

Es justo lo que yo quería decir, pero con palabras bonitas

Que quede claro, Victor Luis, que no tengo nada personal contra ti, saludos.

[Victor Luis]

Holas Nelson y Casimiro...

Me disculpo ante el Foro Delphi y en especial ante ustedes... creo que me excedi un poco pero no es por el foro ni sus organizadores; pero hubo algunos comentarios que estaban fuera de lugar por otros miembros del foro, que manifestaban que publique el codigo sino no te creemos y eso va contra mi manera de ser y mi personalidad, no me conocen, espero un dia si....

○ Se que es un Foro Delphi, el primer lenguaje que aprendi fue Basic en colegio, usando los Atari computer, despues de mucho tiempo todo era diferente y aprendi Pascal y de ahi Delphi con lo que hice varias aplicaciones. Luego consegui Visual Basic y medio me perdi; por lo que empece a usar VBA Excel para hacer programas para mi Laboratorio y despues copie elcodigo a Visual Basic, modifique algo y era casi lo mismo, lo que me resulto mas sencillo....
◘ Pero sera un compromiso... Intensificare mis conocimientos en Delphi... como dice Nelson es un leguaje eficiente... eso tambien lei de Java pero medio voy por ahi...


○ Respecto a lo que dice Casimiro de compartir conocimientos y trucos y mas.... estoy de acuerdo; pero no solo mediante la publicacion de codigo fuente. Si vieron, les comparti el metodo que para mi es simplicado y mejor que Eratostenes, les indique como depurar los multiplos de la secuencia extraida con las sumas +2 +4 y que los multiplos para mi estan en grupos de 2 multiplos, estos saltos o posiciones son propias para los multiplos de cada numero primo y se repiten.
◘ Con esto Casimiro creo estar aportando al foro y al tema en cuestion del Problema al Generar Numeros Primos, el tiempo del proceso se reducira significativamente y podra hacer busquedas de numeros mas grandes... La cosa esta en que quieren el codigo fuente y por ahora no lo tengo en Delphi, pues es un metodo que lo deje de usar porque encontre otros 3 metodos mejores y el 4º fue el que uso ahora...
○ Pero si tienen alguna duda al respecto... estoy predispuesto a brindar mi colaboracion como lo hace mi amigo Nelson...


○ Sobre el ultimo comentario de Nelson dire que lo se amigo...
Gracias por recordarmelo, no soy matematico y mis conocimientos de programacion son del promedio medio o regular y es esto lo que me motiva a seguir adelante.
◘ Un dia publicare mi metodo, luego de ajustar el 2º dato que me falta al pasar el cuatrillon, veran que es verificable y repetible, lo que si no creo poder exponer una formula como los que hay, que no los entiendo; pero estoy seguro que en base a esta logica surgiran formulas e ideas que mejoren la busqueda de numeros primos... al menos esa es mi espectativa.
Por ahora no puedo hacerlo presentar un metodo que esta desarrollado hasta el 95%, soy prudente en ello pues como bien dice Nelson "el mundo académico es ciertamente muy exigente en este sentido"

◘ Bueno amigos me ausentare un tiempo breve por asuntos de trabajo y no les molestare con mis tonterias... espero les vaya bien en el desarrollo del metodo...

NOTA. (para Nelson) Mi hermano Nelson Arteaga que actualmente radica en Puno-Peru tiene acceso a mi equipo y todos mis apuntes de los analisis realizados.
○ Un favor, si sabes de donde puedo descargar un Manual de Delphi 7 en español, te lo agradeceria....

[[nlsgarcia]]

Victor Luis,

Empezado por Victor Luis

...donde puedo descargar un Manual de Delphi 7 en español...

La siguiente información esta en su mayoría en español con algunas excepciones en ingles.

Revisa estos Tutorials de Delphi:

Tutorial Borland Delphi : http://www.programacionfacil.com/borland_delphi/start

Lenguaje Delphi : http://es.wikibooks.org/wiki/Lenguaje_Delphi

Curso de Delphi Básico : http://terawiki.clubdelphi.com/Delph...asico_pdf_.rar

Curso de Delphi Paso a Paso : http://terawiki.clubdelphi.com/Delph..._paso_pdf_.zip

Delphi para Novatos : http://terawiki.clubdelphi.com/Delph...tos__html_.zip

Delphi el Hijo de Pascal : http://terawiki.clubdelphi.com/Delph...ascal_pdf_.rar

Delphi al Límite : http://terawiki.clubdelphi.com/Delph...imite_pdf_.zip

Revisa estos Links:

Delphi Basics : http://www.delphibasics.co.uk/ (Excelente como referencia del lenguaje)

A Beginner's Guide to Delphi Programming : http://delphi.about.com/od/beginners/a/delphicourse.htm (Excelente site para Delphi en general)

Revisa estos libros:

La cara oculta de Delphi 4, Autor Ian Marteens : http://terawiki.clubdelphi.com/Delph...phi_4_pdf_.zip (Es un libro muy recomendado)

Borland Delphi 6 Developer's Guide, Autores: Steve Teixeira And Xavier Pacheco (Internet, es un libro avanzado en Ingles)

La Biblia de Delphi 7, Autor: Marco Cantu. (Internet, es un libro muy interesante en español)

Revisa el FTP del Club Delphi:

Delphi : http://terawiki.clubdelphi.com/Delphi/

Nota: Cuando puedas trasladar el código de tu algoritmo de VB6 a Delphi 7, los tiempos de proceso en general disminuirán de forma considerable.

Suerte

Espero sea útil

Nelson.

[Victor Luis]

Holas Nelson...

Gracias, ya estoy revisando los enlaces o links que adjuntaste...

Antes de publicar el codigo y no lluevan criticas, me gustaria enviartelo a tu correo y le des una chekeada o mirada.... OK

[[nlsgarcia]]

Club Delphi,

Los siguientes programas son un Compendio de Cribas de Generación de Números Primos implementadas en Delphi:

Criba de Eratóstenes:

Código Delphi [-]
program GeneratorPrimeNumbers;

{
Cálculo de Números Primos por el Algoritmo: Criba de Eratóstenes (Versión 2).
}

uses
  Windows, SysUtils, Classes, Dialogs;

var
   Limit, RLimit : Integer;
   i, j: Integer;
   Numbers: TBits;
   F : TextFile;
   NumberPrime : Integer;
   TI, TF: TDateTime;
   Mnsj : String;

begin

   repeat
      try
         Limit := StrToInt(InputBox('Generador de Números Primos',
                                    'Número Primo Máximo a Calcular:', '1000'));
      except
         Limit := 0;
      end;
   until (Limit >= 2) and (Limit <= 2147483615);

   TI := Now;

   try

      Numbers := TBits.Create;
      Numbers.Size := Limit+1;
      RLimit := Trunc(Sqrt(Limit));
      NumberPrime := 0;

      for i := 2 to RLimit do
         if not Numbers[i] then
            for j := i to (Limit div i) do
               Numbers[i*j] := True;

      FileMode := fmOpenWrite;
      AssignFile(F, 'NumberPrime.txt');
      Rewrite(F);

      for i := 2 to Limit do
         if not Numbers[i] then
         begin
            // Writeln(F, Format('%.10d',[i]));
            Writeln(F, i);
            Inc(NumberPrime);
         end;

   finally

      Numbers.Free;
      CloseFile(F);

   end;

   TF := Now - TI;

   ThousandSeparator := '.';
   DecimalSeparator := ',';

   Mnsj := Format('Con el Número %s como Límite, Se Generaron %s Números Primos en %s',
                 [FormatFloat('#,###,###,###,##0',Limit),
                  FormatFloat('#,###,###,###,##0',NumberPrime),
                  FormatDateTime('hh:mm:ss:zzz', TF)
                 ]);

   MessageBox(0, PChar(Mnsj), 'Algoritmo: Criba de Eratóstenes', MB_OK + MB_ICONINFORMATION);

end.

Criba de Atkin:

Código Delphi [-]
program GeneratorPrimeNumbers;

{
Cálculo de Números Primos por el Algoritmo: Criba de Atkin Optimizada
}

uses
  Windows, SysUtils, Classes, Dialogs;

var
   Limit, RLimit : LongWord;
   i, j : Integer;
   n,k : LongWord;
   R1 : LongWord;
   R2 : LongWord;
   xStepsize : LongWord;
   y_limit : LongWord;
   s, min_y, yy : LongWord;

   Numbers : TBits;
   F : TextFile;
   NumberPrime : LongWord;
   TI, TF : TDateTime;
   Msg : String;

begin

   repeat
      try
         Limit := StrToInt(InputBox('Generador de Números Primos',
                                    'Número Primo Máximo a Calcular:', '1000'));
      except
         Limit := 0;
      end;
   until (Limit >= 2) and (Limit <= 2147483615);

   TI := Now;

   Numbers := TBits.Create;

   try

      Numbers.Size := Limit+1;
      RLimit := Trunc(Sqrt(Limit));
      NumberPrime := 0;

      // Inicio del cálculo de 3x^2 + y^2
      xStepsize := 3;
      y_limit := 0;
      n := 0;
      R1 := Trunc(Sqrt((Limit - 1) / 3));

      i := 0;
      while (i < 12 * R1) do
      begin
         xStepsize := xStepsize + i;
         y_limit := 12 * Trunc(Sqrt(Limit - xStepsize)) - 36;
         n := xStepsize + 16;
         j := -12;
         while(j < y_limit + 1) do
         begin
            n := n + j;
            Numbers[n] := not Numbers[n];
            Inc(j,72);
         end;

         n := xStepsize + 4;

         j := 12;
         while (j < y_limit + 1) do
         begin
            n := n + j;
            Numbers[n] := not Numbers[n];
            inc(j,72);
         end;
         inc(i,24);
      end;
      // Fin del cálculo de 3x^2 + y^2

      // Inicio del cálculo de 4x^2 + y^2
      xStepsize := 0;
      R1 := 8 * Trunc(Sqrt((Limit - 1) / 4)) + 4;

      i := 4;
      while (i < R1) do
      begin
         xStepsize := xStepsize + i;
         n := xStepsize + 1;

         if (xStepsize mod 3 <> 0) then
         begin
            R2 := 4 * Trunc(Sqrt(Limit - xStepsize)) - 3;
            j := 0;
            while (j < R2) do
            begin
               n := n + j;
               Numbers[n] := not Numbers[n];
               Inc(j,8);
            end;
         end
         else
         begin
            y_limit := 12 * Trunc(Sqrt(Limit - xStepsize)) - 36;
            n := xStepsize + 25;
            j := -24;
            while (j < y_limit + 1) do
            begin
               n := n + j;
               Numbers[n] := not Numbers[n];
               Inc(j,72);
            end;

            n := xStepsize + 1;

            j := 24;
            while (j < y_limit + 1) do
            begin
               n := n + j;
               Numbers[n] := not Numbers[n];
               inc(j,72);
            end;
         end;
         inc(i, 8);
      end;
      // Fin del cálculo de 4x^2 + y^2

      // Inicio del cálculo de 3x^2 - y^2
      xStepsize := 1;
      R1 := Trunc(Sqrt(Limit/2))+1;

      i := 3;
      while (i < R1) do
      begin
         xStepsize := xStepsize + (4 * i - 4);
         n := 3 * xStepsize;
         s := 4;
         if (n > Limit) then
         begin
            min_y := (Trunc(Sqrt(n - Limit)) shr 2) shl 2;
            yy := min_y * min_y;
            n := n - yy;
            s := 4 * min_y + 4;
         end
         else
            s := 4;

         j := s;
         while (j < 4 * i) do
         begin
            n := n - j;
            if (n <= Limit) and (n mod 12 = 11) then
               Numbers[n] := not Numbers[n];
            Inc(j,8);
         end;
         inc(i,2);
      end;

      xStepsize := 0;
      i := 2;
      while (i < R1) do
      begin
         xStepsize := xStepsize + (4 * i - 4);
         n := 3 * xStepsize;
         s := 0;
         if (n > Limit) then
         begin
            min_y := ((Trunc(Sqrt(n - Limit)) shr 2) shl 2) - 1;
            yy := min_y * min_y;
            n := n - yy;
            s := 4 * min_y + 4;
         end
         else
         begin
            n := n - 1;
            s := 0;
         end;

         j := s;
         while(j < 4 * i) do
         begin
            n := n - j;
            if (n <= Limit) and (n mod 12 = 11) then
               Numbers[n] := not Numbers[n];
            inc(j,8);
         end;
         inc(i,2);
      end;
      // Fin del cálculo de 3x^2 - y^2

      i := 5;
      while (i <= RLimit+1) do
      begin
         if Numbers[i] then
         begin
            k := i*i;
            while (k < Limit) do
            begin
               Numbers[k] := False;
               Inc(k,i*i);
            end;
         end;
         Inc(i,2);
      end;

      FileMode := fmOpenWrite;
      AssignFile(F, 'NumberPrime.txt');
      Rewrite(F);

      Numbers[2] := True;
      Numbers[3] := True;

      for i := 2 to Limit do
         if Numbers[i] then
         begin
            Writeln(F, i);
            Inc(NumberPrime);
         end;

   finally

      Numbers.Free;
      CloseFile(F);

   end;

   TF := Now - TI;

   ThousandSeparator := '.';
   DecimalSeparator := ',';

   Msg := Format('Con el Número %s como Límite, Se Generaron %s Números Primos en %s',
                 [FormatFloat('#,###,###,###,##0',Limit),
                  FormatFloat('#,###,###,###,##0',NumberPrime),
                  FormatDateTime('hh:mm:ss:zzz', TF)
                 ]);

   MessageBox(0, PChar(Msg), 'Algoritmo: Criba de Atkin', MB_OK + MB_ICONINFORMATION);

end.

Criba de Sundaram:

Código Delphi [-]
program GeneratorPrimeNumbers;

{
Cálculo de Números Primos por el Algoritmo: Criba de Sundaram
}

uses
  Windows, SysUtils, Classes, Dialogs;

var
   Limit, RLimit : LongWord;
   i, j, k : LongWord;
   Numbers: TBits;
   F : TextFile;
   NumberPrime : LongWord;
   TI, TF: TDateTime;
   Mnsj : String;
   maxVal : LongWord;
   denominator : LongWord;
   Prime : LongWord;

begin

   repeat
      try
         Limit := StrToInt(InputBox('Generador de Números Primos',
                                    'Número Primo Máximo a Calcular:', '1000'));
      except
         Limit := 0;
      end;
   until (Limit >= 2) and (Limit <= 2147483615);

   TI := Now;

   try

      Numbers := TBits.Create;
      k := Limit div 2;
      Numbers.Size := k + 1;
      NumberPrime := 0;

      maxVal := 0;
      denominator := 0;

      i := 1;
      while(i < k) do
      begin
         denominator := (i shl 1) + 1;
         maxVal := (k - i) div denominator;
         j := i;
         while(j <= maxVal) do
         begin
            Numbers[i + j * denominator] := True;
            inc(j);
         end;
         inc(i);
      end;

      FileMode := fmOpenWrite;
      AssignFile(F, 'NumberPrime.txt');
      Rewrite(F);
      Writeln(F, 2);
      Inc(NumberPrime);

      Prime := 0;
      i := 1;
      while(i < k) do
      begin
         if not Numbers[i] then
         begin
            Prime := (i shl 1) + 1;
            Writeln(F, Prime);
            Inc(NumberPrime);
         end;
         inc(i);
      end;

   finally

      Numbers.Free;
      CloseFile(F);

   end;

   TF := Now - TI;

   ThousandSeparator := '.';
   DecimalSeparator := ',';

   Mnsj := Format('Con el Número %s como Límite, Se Generaron %s Números Primos en %s',
                 [FormatFloat('#,###,###,###,##0',Limit),
                  FormatFloat('#,###,###,###,##0',NumberPrime),
                  FormatDateTime('hh:mm:ss:zzz', TF)
                 ]);

   MessageBox(0, PChar(Mnsj), 'Algoritmo: Sieve of Sundaram', MB_OK + MB_ICONINFORMATION);

end.

Todas las anteriores implementaciones permite calcular con el Número 2.147.483.615 como cota límite, un máximo de 105.097.563 Números Primos en tiempos variables, sobre una máquina con un Procesador Phenom II X6 1090T, 4 GB RAM, 3 TB HDD y Windows 7 Profesional x32, como se muestra en la siguiente imagen a continuación:



El tiempo indicado en la imagen para los diferentes algoritmos es el tiempo total de proceso desde que inicia el cálculo hasta que finaliza la generación del archivo de 1.12 GB con los 105.097.563 Números Primos, lo cual implica que la verificación de los números primos: se hace en un tiempo menor al indicado.

Espero sea útil

Nelson.

[Victor Luis]

Holas Nelson...

La busqueda con el algoritmo de la criba de Eratostenes veo que es muy rapido... 2 minutos 25 segundos es un buen tiempo para un rango de poco mas de 2.000 millones...

○ Mi metodo PRI-BASE lo haria en 41 minutos, aunque ya encontre la forma de archivarlos en la mitad del tiempo que lo hacia, pero como dices el tiempo de busqueda es mas corto y lo que demora es archivar millones de numeros primos.
○ Una consulta al respecto, este tiempo es constante en cada busqueda del limite de 2.147.483.615 y por qué usan esta cantidad y no un limite entero... como 2.000 o 5.000 millones ?
Pregunto porque como indique el tiempo de mi metodo es constante, se cuando terminara no importa si busco en numeros grandes de mas de 18 o 24 digitos...

◘ Queria comentarte que intente poner el codigo en Delphi y he avanzado poco, creo que profundice mas VB, no encuentro las funciones compatibles como: Erase para inicializar un array, los Exponentes como 10^6, redondear hasta ciertos decimales y la funcion Format para dar formato a los numeros con puntos de mil o con decimales y me surge la duda si podre abrir los archivos de primos como otros con los Types que declare en Delphi, caso contrario tendria que iniciar desde 0 la busqueda y lo que queria es comparar los tiempos de las busquedas actuales...

◘ Por otro lado estoy analizando un metodo de Factorizacion para evaluar si un numero grande es primo o no, es una idea que me surgio y si resulta podria implementarlo al programa y ver que depure mayor cantidad de numeros grandes en menor tiempo.


Bueno amigo, para finalizar te dire que pronto tendre mi equipo actualizado con mas GB en el disco, mayor RAM y procesador, con lo que espero realizar busquedas con rangos mas grandes y reducir el tiempo del proceso....

Suerte y Gracias por la informacion que compartes....

[[nlsgarcia]]

Victor Luis,

Empezado por Victor Luis

...este tiempo es constante en cada búsqueda del limite de 2.147.483.615 y por qué usan esta cantidad...

Empezado por Victor Luis

...no encuentro las funciones...Erase para inicializar un array...los Exponentes...redondear...archivos...

Empezado por Victor Luis

...estoy analizando un método de Factorización para evaluar si un numero grande es primo o no...

Te comento:

1- El tiempo de generación de números primos nunca es constante en ningún algoritmo, varia en función de la carga del computador a nivel de recursos, pero en general se mantiene con pocas variaciones. El limite de 2.147.483.615 esta fijado en función de la clase TBits, la cual tiene como tamaño máximo dicho límite, algo similar ocurre con los arrays en Delphi y C#.

2- En lo referente a las funciones equivalentes entre VB6 y Delphi 7 te sugiero revisar este link:

Delphi Basics : http://www.delphibasics.co.uk/

3- Los métodos de factorización y primalidad no son adecuados para ser incluidos en un generador de números primos, dado que los tiempos se incrementarían notablemente, como ejemplo de un método de primalidad incluyo el de Miller-Rabin realizado en C# por tener el tipo BigInteger el cual facilita el uso de números enteros de gran tamaño, adecuado para su uso en algoritmos de números primos:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Security.Cryptography;
using System.Windows.Forms;

namespace MillerRabin
{
    class Program
    {

        static bool IsProbablePrime(BigInteger source)
        {
            int certainty = 10;
            if (source == 2 || source == 3)
                return true;
            if (source < 2 || source % 2 == 0)
                return false;

            BigInteger d = source - 1;
            int s = 0;

            while (d % 2 == 0)
            {
                d /= 2;
                s += 1;
            }

            RandomNumberGenerator rng = RandomNumberGenerator.Create();
            byte[] bytes = new byte[source.ToByteArray().LongLength];
            BigInteger a;

            for (int i = 0; i < certainty; i++)
            {
                do
                {
                    rng.GetBytes(bytes);
                    a = new BigInteger(bytes);
                }
                while (a < 2 || a >= source - 2);

                BigInteger x = BigInteger.ModPow(a, d, source);
                if (x == 1 || x == source - 1)
                    continue;

                for (int r = 1; r < s; r++)
                {
                    x = BigInteger.ModPow(x, 2, source);
                    if (x == 1)
                        return false;
                    if (x == source - 1)
                        break;
                }

                if (x != source - 1)
                    return false;
            }

            return true;
        }

        static void Main(string[] args)
        {
            
            BigInteger Number;
            String AuxNumber;

            do
            {
               AuxNumber = Microsoft.VisualBasic.Interaction.InputBox("Número a Verificar Primalidad", 
                                                                       "Test de Primalidad MillerRabin", "");
               BigInteger.TryParse(AuxNumber, out Number);
               if (IsProbablePrime(Number))
                   MessageBox.Show("Es un Número Primo", "Test de Primalidad MillerRabin", 
                                   MessageBoxButtons.OK, MessageBoxIcon.Information);
               else if (AuxNumber != "")
                   MessageBox.Show("Es un Número Compuesto", "Test de Primalidad MillerRabin", 
                                   MessageBoxButtons.OK, MessageBoxIcon.Information);
            } while (AuxNumber != "");
            
        }
    }
}

El código anterior en C#, permite verificar la primalidad de un número por medio del algoritmo Miller-Rabin aplicado 10 veces por cada Primo Probable, a fin de garantizar su confiabilidad. Estoy revisando librerías que me permitan manejar grandes números enteros para trasladar el código a Delphi.

Pregunto: ¿Podrías explicar como manejas números enteros de 18 y 24 dígitos en VB6?

Espero sea útil

Nelson.