查找下一个素数

Question

我在寻找一种快速且记忆有效的方法来寻找下一个质数。

输入：整数n

输出第一个素数大于n

在Fastest way to list all primes below 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

我绝对推荐某种筛子或过滤器。

在试图解决一个涉及素数的有趣问题时，我在Python中创建了以下内容： https://gist.github.com/anonymous/4960155

我能在15秒内通过几百万个素数，IIRC。过了一会儿。我很高兴我救了它！

Answer 2

我可以想出两种方法来解决这个问题。我最近尝试的第一个——我在C++中做了一个非常有效的Sieve of Eratosthenes，并将它变成了C/C++ Extension for Python。

它的内存效率高，因为它使用位图而不是实际的int数组，而且它非常快-最多10**9，它在一个破旧的单核虚拟机上工作大约20秒（同时将位图导出为实际的int）。在你的例子中，你只能保留位图，如果你现在的绝对最大值是n，你可以预先计算素数。

另一种方法是研究一些Primality tests，但不要忘记其中一些是概率的。

Answer 3

最好的办法显然如下。

1. 在n处开始筛分，直到2n为止，以消除带有小素数的数字。
2. 对剩余的值运行一个概率素数测试程序，如Miller-Rabin。
3. 如果需要，对已报告的第一个质数运行确定性质数测试程序。