<p>我在寻找一种快速且记忆有效的方法来寻找下一个质数。</p>
<p><strong>输入:</strong>整数<code>n</code></p>
<p><strong>输出</strong>第一个素数大于<code>n</code></p>
<p>在<a href="https://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188">Fastest way to list all primes below N</a>打印所有小于<code>n</code>的素数是非常好的代码。我的低效方法目前发现所有小于<code>2n</code>的素数,然后通过循环遍历列表来搜索大于<code>n</code>的第一个素数。这是我现在的密码。</p>
<pre><code>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
</code></pre>
<p>最后一次测试需要将近1GB的内存。这段代码的另一个问题是,如果$n=10**10$,它就会失败。</p>
<p>这个问题能快点解决吗?有没有办法让它用更少的内存?</p>