algorithm - 从数十亿个数字中找出质数

Question

我在某个地方遇到了以下问题，但对我的回答不满意。

qtn: 你已经给出了一个可以是 100 亿个数字的列表。 现在你必须找出其中哪些是素数。

我回答说，要找到素数，我们必须遍历十亿个数的循环 并逐一检查是否是最佳天气。 我们可以在这里进行一些优化检查，如果 no 是 even 我们将不检查，因为素数 no 不能是偶数。 为了存储否，我们可以使用 double 组，因为 double 组的大小为 8 字节，因此它也可以处理十亿个数字。 但他似乎仍然不满意。 请在这里提供帮助，这里的答案可能更合理。 谢谢!

Answer 1

比方说，我们将素数存储在一个数组中。根据Sieve of Eratosthenes :

1. 创建一个从 2 到 10¹⁰ 的连续整数列表:(2, 3, 4, ...., 10¹⁰)。
2. 一开始，令p等于2，即最小的素数。
3. 通过从 2p 开始以 p 为增量计数到 10¹⁰ 来枚举 p 的倍数，并标记它们在列表中(这些将是 2p、3p、4p、....；p 本身应该不被标记)。
4. 在数组中插入p。
5. 在列表中找到第一个大于 p 且未标记的数字。如果没有这样的数字，停止。否则，让 p 现在等于这个新数(这是下一个质数)，并从步骤 3 开始重复。

当算法终止时，您将在数组中存储所有小于 10¹⁰ 的素数。

例子

要找到所有小于或等于 20 的素数，过程将是:

首先生成一个从 2 到 20 的整数列表:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

列表中的第一个数字是 2；通过从 2 以 2 递增计数(这些将是列表中所有 2 的倍数)，在 2 之后划掉列表中的每个第 2 个数字:

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

列表中 2 之后的下一个数字是 3；通过从 3 开始以 3 为增量向上计数，将列表中 3 之后的每第 3 个数字划掉(这些将是列表中所有 3 的倍数):

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

列表中 3 之后尚未划掉的下一个数字是 5；通过从 5 开始以 5 为增量计数(即 5 的所有倍数)，将列表中的每 5 个数字在 5 之后划掉，但此时它们都已被划掉，因为这些数字(10、15、20)也是倍数较小的素数，因为5*5大于20。此时列表中没有划掉的数都是20以下的素数:

2 3     5    7           11       13              17      19

如您所说，为了提高效率，您最初可以只列出奇数，(3, 5, ...., 10⁹)，然后从 2p 开始计数em>p² 在步骤 3 中，因此仅标记 p 的奇数倍。

另一种提高效率的方法是，在第 3 步中标记从 p² 开始的数字，因为 p 的所有较小倍数都已在此处标记观点。这意味着当 p² 大于 10¹⁰ 时，允许算法在第 5 步终止。

如果您的内存不足并且需要生成较小范围内的素数，您也可以查看分段筛。