寻找下一个素数

Question

我在寻找一种快速且节省内存的方法来找到下一个质数。

输入：一个整数 n

输出：第一个比 n 大的质数

在这里有一段很不错的代码，可以打印出所有小于 n 的质数，链接在这里。我现在的方法效率不高，首先找到所有小于 2n 的质数，然后通过遍历这个列表来寻找第一个比 n 大的质数。以下是我目前的代码。

import numpy
def primesfrom2to(n):
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = numpy.ones(n/3 + (n%6==2), dtype=numpy.bool)
    for i in xrange(1,int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[       k*k/3     ::2*k] = False
            sieve[k*(k-2*(i&1)+4)/3::2*k] = False
    return numpy.r_[2,3,((3*numpy.nonzero(sieve)[0][1:]+1)|1)]

n=10**7
timeit next(x for x in primesfrom2to(2*n) if x > n)
1 loops, best of 3: 2.18 s per loop

n= 10**8
timeit next(x for x in primesfrom2to(2*n) if x > n)
1 loops, best of 3: 21.7 s per loop

这个最后的测试几乎占用了1GB的内存。这个代码的另一个问题是，如果 $n = 10**10$，它就会直接失败。

有没有更快的方法解决这个问题？有没有办法让它使用更少的内存？

Answer 1

我想到两种解决这个问题的方法。第一种是我最近尝试的——我用C++写了一个非常高效的埃拉托斯特尼筛法，并把它做成了一个Python的C/C++扩展。

这个方法在内存使用上很高效，因为它用的是位图，而不是实际的整数数组（int）。而且速度也很快——在一个老旧的单核虚拟机上，处理到10的9次方的数字大约只需要20秒（还包括把位图转换成实际的整数）。在你的情况下，你可以只保留位图，如果你知道n的最大值，可以提前计算出素数。

另一种方法是研究一些素性测试，但要记住，有些测试是基于概率的。

Answer 2

我绝对推荐使用某种筛选器或过滤器。

在尝试解决一个关于质数的问题时，我为了好玩用Python写了以下代码： https://gist.github.com/anonymous/4960155

如果我没记错的话，我能在大约15秒内找到几百万个质数。这是之前的事了，我很高兴我把它保存下来了！

Answer 3

最好的做法显然是这样的：

1. 从 n 开始，筛选到 2n，这样可以去掉小质数的数字。
2. 对剩下的数字使用一种概率质数测试方法，比如米勒-拉宾测试。
3. 如果有必要，可以对第一个被报告为质数的数字使用确定性质数测试。