在n和2n之间寻找质数的最快方法是什么？

Question

在考虑Bertrand's postulate的情况下，找到介于n和2n之间的质数最快的方法是什么？这里的n<2^32。

- Bruno Snickers

---

在一个预先填好的从2到2^33-1的素数表中使用二分查找算法。 - Andrew Morton

@BrunoSnickers 是的，但是这样可以很快地找到n和2n之间的质数，这也是你所要求的。也许你想问一个不同的问题，并更详细地解释一下问题？ - Andrew Morton

我认为他在谈论找到一个质数而不是所有的质数。因此，保存比前一个质数小两倍的最大下一个质数就足够了。 - maraca

需要保存的质数数量小于50。 - maraca

@LưuVĩnhPhúc 是的，我可能会使用那个。 - Bruno Snickers

Answer 1

最快的方法可能是预先计算并存储一个大小为2^32的一维数组，其中索引n的值是n和2n之间所需的质数。当然，这会极大地占用内存，但它可能是最快的。

一种稍慢但使用的内存要少得多的方法是预先计算并存储所有“Bertrand质数”的列表，其中第一个元素是第一个质数，每个元素在第一个元素的两倍以下中是最大的质数。您可以使用该列表的二进制搜索快速查找所需的质数。如果你想要1 < n < 2^32，你需要在该列表中将最后一个质数设为大于2^32，以捕捉所有这样的n。那只需要一个包含34个质数的列表，非常可行。顺便说一下，如果你想做到2^64，你只需要66个质数。

这里是实现该算法的Python 3.5代码。它使用标准库中的二进制搜索函数。Bertrand质数列表是用另一个简单的Python例程找到的，虽然它也可以在整数序列在线百科全书，序列A006992中找到。

from bisect import bisect_right

_bertrand_primes = [
             2,          3,          5,          7,         13,         23,
            43,         83,        163,        317,        631,       1259,
          2503,       5003,       9973,      19937,      39869,      79699,
        159389,     318751,     637499,    1274989,    2549951,    5099893,
      10199767,   20399531,   40799041,   81598067,  163196129,  326392249,
     652784471, 1305568919, 2611137817, 5222275627]

def prime_between_n_and_2n(n):
    """Find a prime number p such that n < p < 2n. The returned value
    will be the first 'Bertrand prime' <https://oeis.org/A006992>
    greater than n. n is limited to 1 < n < 2**32 but need not be an
    integer. Outside those limits, None is returned.
    """
    if 1 < n < 2**32:
        return _bertrand_primes[bisect_right(_bertrand_primes, n)]

- Rory Daulton