大量的埃拉托色尼筛法 C++ [英] Sieve of Eratosthenes for large numbers c++

问题描述

就像这个问题，我也在研究埃拉托色尼的筛子.同样来自使用 c++ 的编程原理和实践"一书的第 4 章.我能够正确实现它，并且它完全按照练习要求运行.

Just like this question, I also am working on the sieve of Eratosthenes. Also from the book "programming principles and practice using c++", chapter 4. I was able to implement it correctly and it is functioning exactly as the exercise asks.

#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 个整数，每个 32 位.所以 32/8*2^32=16 GiB 内存.我只有 4 GiB...

Now, how would I be able to handle real big numbers in the amount input? The unsigned int type should allow me to enter a number of 2^32=4,294,967,296. But I can't, I run out of memory. Yes, I've done the math: storing 2^32 amount of int, 32 bits each. So 32/8*2^32=16 GiB of memory. I have just 4 GiB...

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

So what I am really doing here is setting non-primes to zero. So I could use a boolean. But still, they would take 8 bits, so 1 byte each. Theoretical I could go to the limit for unsigned int (8/8*2^32=4 GiB), using some of my swap space for the OS and overhead. But I have a x86_64 PC, so what about numbers larger than 2^32?

知道质数在密码学中很重要，必须有更多这样做的有效方法?还有其他方法可以优化找到所有这些素数所需的时间吗?

Knowing that primes are important in cryptography, there must be a more efficient way of doing this? And are there also ways to optimize the time needed to find all those primes?

推荐答案

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

In the sense of storage, you could use the std::vector<bool> container. Because of how it works, you have to trade in speed for storage. Because this implements one bit per boolean, your storage becomes 8 times as efficient. You should be possible to get numbers close to 8*4,294,967,296 if you have all your RAM available for this one program. Only thing you need to do, is use unsigned long long to unleash the availability of 64 bit numbers.

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

Note: Testing the program with the code example below, with an amount input of 8 billion, caused the program to run with a memory usage of approx. 975 MiB, proving the theoretical number.

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

You can also gain some time, because you can declare the complete vector at once, without iteration: vector<bool>numbers (amount, true); creates a vector of size equal to input amount, with all elements set to true. Now, you can adjust the code to set non-primes to false instead of 0.

此外，一旦您按照筛网达到数量的平方根，所有保持真实的数字都是素数.插入 if (p * p >= amount) 作为附加的 continue 条件，就在您输出素数之后.此外，这对您的处理时间来说也是一个小小的改进.

Furthermore, once you have followed the sieve up to the square root of amount, all numbers that remain true are primes. Insert if (p * p >= amount) as an additional continue condition, just after you output the prime number. Also this is a humble improvement for your processing time.

编辑:在最后一个循环中，可以对p进行平方，因为直到p平方为止的所有数字都已经被证明不是由以前的数字组成的素数.

Edit: In the last loop, p can be squared, because all numbers until the square of p are already proved not to be primes by previous numbers.

你应该得到这样的结果:

All together you should get something like this:

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

这篇关于大量的埃拉托色尼筛法 C++的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！