determinar rápidamente si un número es primo en Python para los números <1 mil millones

Question

Mi algoritmo actual para comprobar la primalidad de los números en Python es manera de retardar de los números entre 10 millones y 1 mil millones. Quiero que se mejore sabiendo que nunca recibiré números mayores a mil millones.

El contexto es que no puedo obtener una implementación que sea lo suficientemente rápida para resolver el problema 60 del proyecto Euler: obtengo la respuesta al problema en 75 segundos donde lo necesito en 60 segundos. http://projecteuler.net/index.php?section=problems&id=60

que tienen muy poca memoria a mi disposición lo que no puede almacenar todos los números primos por debajo de 1 mil millones.

actualmente estoy usando la división de prueba estándar sintonizado con 6k ± 1. ¿Hay algo mejor que esto? ¿Ya necesito obtener el método de Rabin-Miller para los números que son tan grandes?

primes_under_100 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] 
def isprime(n): 
    if n <= 100: 
     return n in primes_under_100 
    if n % 2 == 0 or n % 3 == 0: 
     return False 

    for f in range(5, int(n ** .5), 6): 
     if n % f == 0 or n % (f + 2) == 0: 
      return False 
    return True 

¿Cómo puedo mejorar este algoritmo?

Precisión: Soy nuevo en Python y me gustaría trabajar con Python 3+ solamente.

---

código final

Para aquellos que estén interesados, utilizando las ideas de MAK, que genera el siguiente código que es aproximadamente un tercio más rápido, lo que me permite obtener el resultado del problema de Euler en menos de 60 segundos!

from bisect import bisect_left 
# sqrt(1000000000) = 31622 
__primes = sieve(31622) 
def is_prime(n): 
    # if prime is already in the list, just pick it 
    if n <= 31622: 
     i = bisect_left(__primes, n) 
     return i != len(__primes) and __primes[i] == n 
    # Divide by each known prime 
    limit = int(n ** .5) 
    for p in __primes: 
     if p > limit: return True 
     if n % p == 0: return False 
    # fall back on trial division if n > 1 billion 
    for f in range(31627, limit, 6): # 31627 is the next prime 
     if n % f == 0 or n % (f + 4) == 0: 
      return False 
    return True 

Answer 1

Para números tan grandes como 10^9, un enfoque puede ser generar todos los primos hasta sqrt (10^9) y luego simplemente verificar la divisibilidad del número de entrada con los números en esa lista. Si un número no es divisible por ningún primo menor o igual que su raíz cuadrada, debe ser un primo (debe tener al menos un factor < = sqrt y otro> = sqrt para no ser primo). Observe cómo no es necesario probar la divisibilidad para todos los números, solo hasta la raíz cuadrada (que es alrededor de 32,000, bastante manejable, creo). Puede generar la lista de números primos utilizando sieve.

También puede ir a dar un probabilistic prime test. Pero pueden ser más difíciles de entender, y para este problema basta con usar una lista generada de primos.

Answer 2

primera Puede dividir su n solamente por su primes_under_100.

Además, precompute más primos.

También, en realidad estás almacenará el resultado en la memoria range() - Utilización irange() lugar y utilizar esta memoria para ejecutar Sieve of Eratosthenes algorithm.

Answer 3

Para resolver problemas de Project Euler hice lo que sugiere en su pregunta: Implemente la prueba Miller Rabin (en C# pero sospecho que será rápido en python). El algoritmo no es tan difícil. Para números por debajo de 4,759,123,141 es suficiente verificar que un número sea un fuerte pseudoprimer a las bases 2, 7, 61. Combine eso con la división de prueba con primos pequeños.

No sé cómo muchos de los problemas se han resuelto hasta ahora, pero tener un test de primalidad rápida a su disposición a ser de gran valor para muchos de los problemas.