1

我正在寻找一种快速且内存高效的方法来找到下一个素数。

输入：一个整数n

输出第一个大的素数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 的 RAM。这段代码的另一个问题是，例如，如果 $n = 10**10$ 就会失败。

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

4

3 回答 3

2

最好的方法显然如下。

  1. n在直到2n消除具有小素数的数字时开始筛子。
  2. 对剩余值运行概率素数测试器，例如 Miller-Rabin。
  3. 如果需要，对已报告为素数的第一个数运行确定性素数测试器。
于 2013-02-24T10:29:21.297 回答
1

我可以想到两种解决方法。我最近尝试的第一个 - 我在 C++ 中制作了一个非常有效的 Eratosthenes 筛，并将其变成了Python 的 C/C++ 扩展。

它的内存效率很高，因为它使用位图而不是实际的ints 数组，而且速度非常快 - 最多 10**9 它在一个破旧的核心虚拟机上工作大约 20 秒（以及将位图导出为实际整数）。在您的情况下，您只能保留位图，如果您现在n可以预先计算素数的绝对最大值。

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

于 2013-02-15T12:27:45.583 回答
1

我肯定会推荐某种筛子或过滤器。

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

IIRC，我能够在大约 15 秒内通过几百万个素数。这是不久前的事了。我很高兴我保存了它！

于 2013-02-15T12:40:29.883 回答