[pyar] Numeros primos

[Matias Graña]

2011/11/25 Ricardo Armas <rarmas en gmail.com>:
> On Fri, Nov 25, 2011 at 13:00, Matias Graña <matias.alejo en gmail.com> wrote:
>
>> Es que el problema original era encontrar TODOS los números primos,
>> empezando desde el 2. Vos lo estás cambiando por encontrar ALGUNOS
>> números primos entre dos valores. Ambos problemas son importantes,
>> pero son distintos, y no se suelen resolver de la misma manera.
>
> si cambiás el código de main() por esto
>
> def main(argv):
>  for p in range(2,int(argv[0])):
>    if MillerRabin(p):
>      print(p)
>
> El programa imprime TODOS los primos desde el 2 y bastante más rápido
> que la criba...

Sí, asumiendo la hipótesis de Riemann. De todas maneras, la HR a esta
altura es dudoso que sea falsa, y es cierto que hay un factor de
ln(n)^2 con MillerRabin y de n/ln(n) con la criba, que es bastante más
grande.
Alguien sabe si en la práctica se usa AKS?
http://en.wikipedia.org/wiki/AKS_primality_test

Matías