c++ - 大数埃拉托色尼筛法 C++

Question

就这样question ，我也在研究埃拉托色尼筛法。同样来自 “使用 C++ 编程原则和实践” 的书，第 4 章。我能够正确地实现它，并且它的功能完全符合练习要求。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    unsigned int amount = 0;

    cin >> amount;

    vector<int>numbers;

    for (unsigned int i = 0; i <= amount; i++) {
        numbers.push_back(i);
    }

    for (unsigned int p = 2; p < amount; p++) {
        if (numbers[p] == 0)
            continue;

        cout << p << '\n';

        for (unsigned int i = p + p; i <= amount; i += p) {
            numbers[i] = false;
        }
    }

    return 0;
}

现在，我将如何处理 amount 输入中的真正大数字？ unsigned int 类型应该允许我输入一个数字 2^32=4,294,967,296。但是我不能，我的内存用完了。是的，我计算过:存储 2^32 个 int，每个 32 位。所以 32/8*2^32=16 GiB 内存。我只有 4 GiB...

所以我在这里真正要做的是将非素数设置为零。所以我可以使用 bool 值。但是，它们仍然需要 8 位，所以每个 1 个字节。理论上我可以达到 unsigned int (8/8*2^32=4 GiB) 的限制，使用操作系统和开销的一些交换空间。但是我有一台 x86_64 PC，那么大于 2^32 的数字呢？

知道质数是 important in cryptography ，必须有更有效的方法来做到这一点？还有其他方法可以优化找到所有这些素数所需的时间吗？

Answer 1

在存储方面，您可以使用 std::vector<bool>容器。由于它的工作方式，您必须以 speed 进行交易用于存储。因为这实现了每个 bool 值一位，所以您的存储效率提高了 8 倍。如果您的所有 RAM 都可用于这个程序，您应该可以获得接近 8*4,294,967,296 的数字。您唯一需要做的就是使用 unsigned long long释放 64 位数字的可用性。

注意:使用下面的代码示例测试程序，输入 80 亿的数量，导致程序运行时内存使用量约为。 975 MiB，证明了理论数字。

您还可以获得一些时间，因为您可以一次声明完整的 vector ，而无需迭代:vector<bool>numbers (amount, true);创建一个 size 等于输入 amount 的 vector ，所有元素都设置为 true。现在，您可以调整代码以将非素数设置为 false 而不是 0。

此外，一旦您按照筛选 直到数量 的平方根，所有保持正确 的数字都是素数。插入 if (p * p >= amount)作为附加的 continue 条件，就在您输出质数之后。这对您的处理时间来说也是一个微不足道的改进。

编辑:在最后一个循环中，p可以平方，因为所有数字直到p的平方已经被前面的数证明不是素数。

你应该得到这样的东西:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    unsigned long long amount = 0;

    cin >> amount;

    vector<bool>numbers (amount, true);

    for (unsigned long long p = 2; p < amount; p++) {
        if ( ! numbers[p])
            continue;

        cout << p << '\n';

        if (p * p >= amount)
            continue;

        for (unsigned long long i = p * p; i <= amount; i += p) {
            numbers[i] = false;
        }
    }

    return 0;
}