Help!

[pplu]

Julià, ¿te atreves a generar todos los primos hasta el (2^32)-1?

A mi me da un poco de miedo porque el tiempo me parece que crece exponencialmente. Tendriamos que llegar al 4.294.967.295. Y solo hemos generado hasta el 1.000.000

Resulta que solo llevamos el 0,02% de la tabla hecha...

Podriamos intentar con un algoritmo que fuera guardando los primos encontrados dentro de un array y ir dividiendo solo entre esos..

Podemos inicializar tranquilamente el array con el 2 y 3 en la primera y segunda posicion (ya vereis porque no meto al 1 en el saco)

procedure EncuentraPrimos()
arrayPrimos := [2,3];
arrayPrimosLibre := 2; 

For probando:=5 to 4294967295 step +2 do begin
i = 0
    while (arrayPrimos[i]<sqrt(probando)) And (not Divisible) do
        if (probando mod arrayPrimos[i] = 0) 
            Divisible: = true;
        else
            i++;
    end
    if not Divisible begin
        arrayPrimos[arrayPrimosLibre] = probando;
        arrayPrimosLibre++;
        (*)
    end
end

end;

Cuidado: Tenemos que usar unsigned integers. para llegar a (2^32)-1

Se que el codigo no es perfecto... lo he escrito tal y como me salia... y posiblemente haya mezclado lenguajes... pero creo que se entiende lo suficiente

Intento recorrer la tabla de primos desde la posicion 0 hacia delante, porque me parece más probable que el numero que estemos probando sea divisible por los numeros más bajitos. Estais de acuerdo conmigo?

He sacado el 1 fuera de la tabla de primos por razones obvias, y ya puestos podriamos sacar el 2, porque no vamos a caer nunca en numeros pares

Y ya se que los arrays no son tan genersos... habria que redimensionarlo cada tanto en cuanto... yo lo haria de 1000 en 1000 posiciones de golpe... asi ahorramos tiempo precioso... y solo tenemos que hacer
if (arrayPrimosLibre mod 1000 = 0) SetLength(arrayPrimos, arrayPrimosLibre + 1000);
donde he puesto el (*)

Si no, podemos intentar estimar el tamaño final que tendrá la tabla, y redimensionar en caso de "urgencia"

Os gusta?