使用Sets,C++计算素数

Question

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

我试图为N = 10的值实现此方法.

选择一个整数n.此函数将计算最多n的所有素数.首先将1到n中的所有数字插入到集合中.然后擦除2的所有倍数(2除外); 也就是说,4,6,8,10,12 ......消除所有3的倍数,即6,9,12,15 ....... 上升到sqrt(n).剩下的数字都是素数.

当我运行我的代码时,它会删除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;
    }
}

演示.