使用集合计算质数，C++

Question

我正在尝试使用集合来计算素数，但是当我进行计算时，我的迭代器随机跳跃。

我正在尝试为 N=10 的值实现此方法。

Choose an integer n. This function will compute all prime numbers up to n. First insert all numbers from 1 to n into a set. Then erase all multiples of 2 (except 2); that is, 4, 6, 8, 10, 12, .... Erase all multiples of 3, that is, 6, 9, 12, 15, ... . Go up to sqrt(n) . The remaining numbers are all primes.

当我运行我的代码时，它擦除 1 然后 pos 跳到 4？我不确定为什么会发生这种情况，而不是它转到值 2，即集合中的第二个值？

此外，在我擦除迭代器指向的值后会发生什么，然后迭代器指向什么，如果我推进它，它会推进到哪里？

代码如下：

set<int> sieveofEratosthenes(int n){ //n = 10

    set<int> a;
    set<int>::iterator pos = a.begin();

//generate set of values 1-10
    for (int i = 1; i <= n; i++) {
        a.insert(i);
        if(pos != a.end())
            pos++;
    }

    pos = a.begin();

    //remove prime numbers
    while (pos != a.end())
    {
        cout << "\nNew Iteration \n\n";

        for (int i = 1; i < sqrt(n); i++) {
            int val = *pos%i;

            cout << "Pos = " << *pos << "\n";
            cout << "I = " << i << "\n";
            cout << *pos << "/" << i << "=" << val << "\n\n";

            if (val == 0) {
                a.erase(i);
                }
            }
        pos++;
    }
    return a;
}

Answer 1

您的实施是不正确的，因为它试图将筛选算法与尝试除数的简单算法结合起来，但没有成功。您不需要测试可除性来实现筛子——事实上，这是算法之美的主要贡献者！你甚至不需要乘法。

a.erase(1);
pos = a.begin();
while (pos != a.end()) {
    int current = *pos++;
    // "remove" is the number to remove.
    // Start it at twice the current number
    int remove = current + current;
    while (remove <= n) {
        a.erase(remove);
        // Add the current number to get the next item to remove
        remove += current;
    }
}

Demo.

Answer 2

擦除循环内的元素时，必须小心索引。例如，当您擦除位置 0 处的元素时，下一个元素现在位于位置 0。因此循环应如下所示：

    for (int i = 1; i < sqrt(n); /*no increment*/) {
        /* ... */
        if (val == 0) {
            a.erase(i);
        } else {
            i++;
        }
    }

实际上，您还必须注意在擦除元素时集合的大小正在缩小。因此你最好使用迭代器：

    for (auto it = a.begin(); i != a.end(); /*no increment*/) {
        /* ... */
        if (val == 0) {
            a.erase(it);
        } else {
            it++;
        }
    }

PS：以上内容并不是筛子所需要的，但足以演示如何擦除元素（我希望如此）。

使用集合计算质数，C++

Calculating Prime Numbers using Sets, C++

c++

pointers

iterator

set