我正在寻找一种快速而高效的内存查找下一个素数的方法。
输入：整数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的RAM。此代码的另一个问题是，例如，如果$ n = 10 ** 10 $，它只会失败。
这个问题可以更快地解决吗？有没有办法让它使用更少的内存？
最佳答案
最好的方法显然如下。
在n处开始筛，直到2n以消除带有小质数的数字。
在其余值上运行概率质数测试仪，例如Miller-Rabin。
如果需要，对报告为素数的第一个数字运行确定性素数测试仪。
关于python - 寻找下一个素数，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14894465/