Déterminez rapidement si un nombre est élevé dans Python pour les chiffres <1 milliard

Mon algorithme actuel pour vérifier la primalité des nombres dans Python est de ralentir pour des chiffres compris entre 10 et 1 milliard. Je veux que cela soit amélioré en sachant que je n'aurai jamais des chiffres de plus de 1 milliard.

Le contexte est que je ne peux pas avoir une implémentation suffisante pour résoudre le problème 60 du projet Euler: je reçois la réponse au problème en 75 secondes où j'en ai besoin dans 60 secondes. http://projecteuler.net/index.php?section=problèmes&id=60 P>

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

Je suis actuellement à l'aide de la division d'essai standard à l'aide de 6K ± 1 . Y a-t-il quelque chose de meilleur que cela? Dois-je déjà obtenir la méthode Rabin-Miller pour des chiffres qui sont ce grand. P> xxx pré>

Comment puis-je améliorer cet algorithme? P>

précision: i 'M NOUVEAU à Python et souhaitez travailler avec Python 3+ uniquement. P>

code final strong> P>

pour ceux qui sont intéressés, en utilisant maks Idées, j'ai généré le code suivant qui correspond à environ 1/3 plus rapide, me permettant d'obtenir le résultat du problème d'Euler en moins de 60 secondes! P>

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