Rapidement déterminer si un nombre est premier en Python pour les numéros de < 1 milliard de dollars

Mon algorithme actuel de vérifier la primalité des nombres en python est lent pour les nombres entre 10 millions et 1 milliard de dollars. Je veux qu'il soit améliorée, en sachant que je n'obtiendrai jamais de nombre plus grand que 1 milliard de dollars.

Le contexte, c'est que je ne peut pas obtenir une mise en œuvre qui est assez rapide pour la résolution du problème de 60 de projet Euler: je reçois la réponse au problème en 75 secondes où j'en ai besoin en 60 secondes. http://projecteuler.net/index.php?section=problems&id=60

J'ai très peu de mémoire à ma disposition donc je ne peux pas stocker tous les nombres premiers inférieurs à 1 milliard de dollars.

Je suis actuellement en utilisant le standard de la division de première instance à l'écoute avec 6k±1. Est-il rien de mieux que cela? Dois-je déjà besoin pour obtenir le Rabin-Miller méthode pour les nombres qui sont de cette de grands.

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

Comment puis-je améliorer cet algorithme?

Précision: je suis nouveau sur python et voudrais travailler avec python 3+.

---

Code Final

Pour ceux qui sont intéressés, à l'aide de MAK idées, j'ai généré le code suivant qui est d'environ 1/3 plus rapide, ce qui me permet d'obtenir le résultat de la droite d'euler problème en moins de 60 secondes!

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

OriginalL'auteur Olivier Grégoire | 2010-12-28