大量埃拉托色尼筛c

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;
}

现在，我怎样才能在输入的量中处理真正的大数字？无符号int类型应该允许我输入2^32=4,294,967,296的数字。但是我不能，我运行内存溢出。是的，我已经计算过了：存储2^32量的int，每个32位。所以32/8*2^32=16 GiB的内存。我只有4 GiB……

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

知道质数在密码学中很重要，一定有更有效的方法来做到这一点？还有没有方法可以优化找到所有这些质数所需的时间？

Answer 1

你问了几个不同的问题。

对于高达2**32的素数，筛分是合适的，但您需要分段工作，而不是在一个大博客中工作。我在这里的答案告诉了如何做到这一点。

对于非常大的密码素数，该过程是挑选一个数，然后使用概率测试来测试它的素性，例如米勒-拉宾测试或贝利-瓦格斯塔夫测试。这个过程并不完美，有时可能会选择复合而不是质数，但这种情况非常罕见。

Answer 2

在存储的意义上，您可以使用 std：：向量

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

您还可以获得一些时间，因为您可以一次声明完整向量，而无需迭代：向量

此外，一旦你顺着筛子找到了数量的平方根，所有仍然为真的数字都是质数。插入<代码> if (p * p

编辑：在最后一个循环中，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;
}