[pyar] Numeros primos

[Claudio Freire]

2011/12/1 Matias Graña <matias.alejo en gmail.com>:
> P(x primo) ~ 1/log x

Perdón, si, lo que puse es ridículo, por responder a los apurones.

> y la cantidad de primos hasta M es O(M/log M).

Otra ridiculez por apurarme. Igual, la densidad de primos decrece
considerablemente en números grandes.

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

Recordá, pedí los primos entre 10^200 y 10^210.

La cantidad de
a = # hasta 10^200 ~ 10^(200-2)
b = # hasta 10^210 ~ 10^(210-2)

b-a = 10^208 - 10^198 ~ 10^208 ~ 2^691 ~ 128PB

128PB de almacenamiento no es impensable. Es mucho, pero no impensable.

Ahora, con la criba, necesitás realizar 10^198 pasadas sobre esos 128PB.
Con Rabin-Miller, una.

> pero para el caso es lo mismo: no te salva ningún test.

Creo que sí.