[pyar] Numeros primos

[Roberto Alsina]

On 11/25/2011 1:33 PM, Matias Graña wrote:
> 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.

La HR está verificada numéricamente para los primeros 10 triillones de 
raíces no triviales.
O sea, no creo que en la práctica te encuentres un número que falle con  
Miller Rabin ;-)