algorithm - 枚举大（20 位）[可能的]素数

Question

给定 A，在 10^20 的数量级上，我想快速获得前几个大于 A 的素数的列表。好吧，我的需求不是那么精确 - 如果偶尔有一个合数结束也没关系在名单上。

枚举大于 A 的（可能的）素数的最快方法是什么？

有没有比遍历所有大于 A 的整数（除了明显的倍数，比如 2 和 3）并为每个整数执行素数测试更快的方法？如果不是，唯一的方法是测试每个整数，我应该使用什么素数测试？

Answer 1

好问题。这仍然没有被证明是多项式时间（位数的多项式，这里是 20）——这是寻找素数博学的项目，几位数学家（包括菲尔兹奖得主 Terence Tao 和 Tim Gowers！）试图提出一个算法，但该项目似乎还没有任何具体的结果。

无论如何，您可以做几件事。正如您和其他人所指出的那样，其中之一是尝试每个数字并检查它是否是素数，使用像Miller-Rabin这样的快速素数测试。通过著名的数论启发式（基于素数定理），n 附近的一个数成为素数的“概率”约为 1/ln(n)，因此对于 10^20，大约每 46 个数字将是主要。因此，如果您想要 k 个 20 位数字，您将对大约 50k 个数字运行 Miller-Rabin 测试。

第二种方法，我认为如果你对许多 A （没有仔细考虑）这样做可能会更快，而是使用筛子，比如Eratosthenes 的筛子。如果您想要 k 个素数，请制作一个包含大约 50k 个数字（或更多以确保安全）的数组，然后筛选它们。您将从预先计算的小于某个数字的素数列表开始。（10 ¹⁰是完全正确的，但是由于您愿意容忍一些合数，因此可以使用较小的素数列表，例如通过前 5000 万个素数进行测试，确保您的数字没有低于 982,451,653 的素数，并且不是很多。）

第三种方法是为这个问题找到别人的实现。:-) 例如，有一个网页给出了一个数字，找到下一个素数或找到下一个十个素数。如果您在线使用它，您似乎必须手动将它们复制下来，但源代码也可用。

Answer 2

有没有比遍历所有大于 A 的整数（除了明显的倍数，比如 2 和 3）并为每个整数执行素数测试更快的方法？

不，没有素数测试就无法知道一个数字是否为素数。

但是，您可以非常快速地对任何数字执行概率素性检验，例如Miller-Rabin 。这是一种安全且广为接受的寻找大素数的方法。由于素数相对丰富，使用这种方法在任何范围内都可以轻松找到素数。只需使用经过测试且高效的 Miller-Rabin 实现，就可以了。

Answer 3

您能做的最好的事情就是生成一个合理的候选者，然后对其进行测试。Miller-Rabin 检验满足您给出数字为素数的高概率的要求，并且您可以根据您使用的迭代次数将复合滑过的机会降低到或多或少的任意水平。

Answer 4

素数是安静的频繁数。素数的频率是 log(n)，这意味着平均每个第 46 个数字是素数，其中 n=10^20。这意味着检查每个数字的素数并不是这样的开销。