[pyar] Numeros primos

[Matias Graña]

> 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

1PB ~ 2^50, así que 2^691 ~ 2^641PB. Es absolutamente impensable. Al
menos para mí.

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

Un test de primalidad para un número del orden de N con RM insume
alrededor de ln^4(N).
Encontrar todos los primos entre 10^200 y 10^210 con RM es del orden de
10^210 * ln^4(10^210). Encontrarlos con la criba es del orden de
10^210 * 10^210 / ln(10^210), que es espantosamente más grande, pero
no menos abarcable hoy en día que RM.
La gran ventaja de RM en la práctica, para mí, es cuando querés
encontrar algunos primos en esos valores, precisamente porque la criba
requiere generarlos todos.
O cuando querés encontrar todos los menores a un número sensiblemente
menor que 10^200 y que se pueda hacer realmente, pero suficientemente
grande como para que valga la pena programar RM en lugar de la criba.
Como dijeron varios, acá ya es una cuestión de métricas.

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

Matías