algorithm - 在 n 和 2n 之间找到质数的最快方法是什么

Question

在 n 之间找到质数的最快方法是什么？和 2n ，考虑到 n<2^32 .我说的是 Bertrand 的假设

Answer 1

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

一种使用更少内存的稍微慢一点的方法是预先计算并存储所有“Bertrand primes”的列表，其中第一个元素是第一个 素数和第一个元素之后的每个元素都是最大的素数 小于前一个元素的两倍。您可以使用该列表的二进制搜索来快速找到所需的素数。如果你想要1 < n < 2^32您需要该列表中的最后一个素数高于 2^32捕获所有这些n .那将需要一个仅包含 34 个质数的列表，非常可行。顺便说一下，如果你想这样做到 2^64你只需要 66 个素数。

这是实现该算法的 Python 3.5 代码。它使用标准库中的二进制搜索功能。 Bertrand 素数列表是通过另一个简单的 Python 例程找到的，尽管它也可以在 The Online Encyclopedia of Integer Sequences 中找到。 , 序列 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)]