[pyar] Numeros primos

[Claudio Freire]

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