在 Python 中快速确定小于 10 亿的数字是否为素数

我目前在 python 中检查数字素数的算法对于 1000 万到 10 亿之间的数字来说速度很慢。我希望它能够得到改进，因为我知道我永远不会得到超过 10 亿的数字。

背景是我无法获得足够快的实现来解决项目 Euler 的问题 60：我在 75 秒内得到问题的答案，而我需要在 60 秒内得到答案。

我的可用内存很少，所以我无法存储 10 亿以下的所有素数。

我目前使用的是用 6k±1 调校的标准试除法。还有比这更好的事情吗？对于这么大的数字，我是否已经需要获取 Rabin-Miller 方法？

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

我该如何改进这个算法？

Precision：我是 python 新手，只想使用 python 3+。

最终代码

对于那些有兴趣的人，使用 MAK 的想法，我生成了以下代码，速度大约快了 1/3，使我能够在不到 60 秒的时间内得到欧拉问题的结果！

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

对于大到 10^9 的数字，一种方法是生成 sqrt(10^9) 以内的所有素数，然后简单地检查输入数字与该列表中的数字的整除性。如果一个数不能被小于或等于其平方根的任何其他素数整除，则它本身必须是素数（它必须至少有一个因子 = sqrt 才不是素数）。请注意，您不需要测试所有数字的整除性，只需测试平方根（大约 32,000 - 我认为相当容易管理）。您可以使用以下命令生成素数列表sieve http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

你也可以去概率素数检验 http://en.wikipedia.org/wiki/Primality_test#Probabilistic_tests。但它们可能更难理解，对于这个问题，只需使用生成的素数列表就足够了。