Eratosthenes筛选大量c ++

Question

就像这个问题一样,我也在研究Eratosthenes的筛子.同样来自"编程原理和使用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 ......

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

知道素数在密码学中很重要,必须有一种更有效的方法吗？还有办法优化找到所有这些素数所需的时间吗？

Answer 1

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

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

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

此外,一旦你跟着筛子达到金额的平方根,所有保持为真的数字都是素数.在输出素数后立即插入if (p * p >= amount)另一个继续条件.这也是您处理时间的一个不起眼的改进.

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