c++ - 使用集合计算质数，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.