快速判断小于10亿的数字是否为质数的Python方法

Question

我现在用来检查数字是否是质数的算法在处理1000万到10亿之间的数字时太慢了。我想要改进这个算法，因为我知道我不会遇到超过10亿的数字。

背景是，我找不到一个足够快的实现来解决Project Euler的第60个问题：我得到的答案需要75秒，而我需要在60秒内完成。http://projecteuler.net/index.php?section=problems&id=60

我可用的内存非常有限，所以我不能存储所有小于10亿的质数。

我现在使用的是标准的试除法，并且进行了6k±1的优化。有没有比这个更好的方法？我是否需要使用拉宾-米勒算法来处理这么大的数字。

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

我该如何改进这个算法呢？

补充说明：我刚接触Python，只想使用Python 3及以上版本。

---

最终代码

对于感兴趣的人，使用MAK的想法，我生成了以下代码，速度快了大约三分之一，让我能在不到60秒内得到Euler问题的结果！

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

你可以先用你的 n 除以所有小于100的质数。

另外，可以提前计算出更多的质数。

还有，你其实是把 range() 的结果存储在内存里——可以用 irange() 来代替，这样就能把内存用来运行埃拉托斯特尼筛法。

Answer 2

为了破解Project Euler的问题，我做了你在问题中提到的事情：实现了米勒-拉宾素性测试（我用的是C#，但我觉得在Python中也会很快）。这个算法其实并不复杂。对于小于4,759,123,141的数字，只需要检查一个数字是否对2、7和61这三个基数是强伪素数。然后再结合用小素数进行试除法。

我不知道你已经解决了多少个问题，但拥有一个快速的素性测试工具，对很多问题来说会非常有帮助。

Answer 3

对于像10^9这么大的数字，一种方法是先生成所有小于等于10^9平方根的质数，然后检查输入的数字是否能被这些质数整除。如果一个数字不能被任何小于或等于它平方根的质数整除，那它就一定是质数（因为要是一个数字不是质数，它至少得有一个小于等于平方根的因子和一个大于平方根的因子）。注意，你只需要测试到平方根的数值就可以了，这个值大约是32,000，处理起来还是比较简单的。你可以使用埃拉托斯特尼筛法来生成质数列表。

你也可以选择使用概率质数测试。不过这些测试可能比较难理解，而对于这个问题，简单地使用生成的质数列表就足够了。