[pyar] Numeros primos

[Claudio Freire]

2011/11/25 Facundo Batista <facundobatista en gmail.com>:
> El problema con la Criba de Eratóstenes es que tenés que arrancar
> poniendo un límite, pero funciona, :)

10 veces mejor que la criba, para números pequeños, es el test
probabilístico de Rabin-Miller[0].

Lo bueno de ese test, es que tiene tiempo costante. Lo mejor aún, es
que para números chicos (32 bits o menores), es demostradamente
determinístico[1].

[0] http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
[1] http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test#Deterministic_variants_of_the_test