[pyar] Numeros primos

[Matias Graña]

2011/12/1 Claudio Freire <klaussfreire en gmail.com>:
> 2011/11/30 Daniel Moisset <dmoisset en machinalis.com>:
>> Ese problema no sale ni con la criba, ni con el test de Rabin-Miller,
>> ni con Maradona-Pelé, ni con la baticomputadora de Bruno Díaz.
>>
>> Con esas magnitudes no te va a alcanzar el sistema solar para guardar
>> el resultado, ni la edad del universo para computarlo, aunque tengas
>> un test que sea O(1) en tu supercomputadora de 1 THz.
>
> Creo que estás olvidando que la densidad de primos es logarítmica.
>
> O sea, P(x primo) ~ log x
>
> Lo que quiere decir que la cantidad de memoria para guardar los primos
> hasta 10^N crece como O(N).

P(x primo) ~ 1/log x, y la cantidad de primos hasta M es O(M/log M).
La cantidad de primos hasta 10^100 es aproximadamente (10^100 / (100 log(10)) ).
En realidad, se parece mucho más a la integral de 2 a 10^100 de
1/log(x), pero para el caso es lo mismo: no te salva ningún test.
Creo que hay más primos < 10^100 que átomos en el universo (aunque acá
cito estimaciones de memoria y quizás le pifie).

Matías