[pyar] Numeros primos

[Luis I. Facciolo]

Aca hay una implementacion de lo mencionado por Claudio:

http://snippets.dzone.com/posts/show/4200


El día 25 de noviembre de 2011 10:56, Claudio Freire
<klaussfreire en gmail.com> escribió:
> 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
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de Argentina - http://www.usla.org.ar
>