c++ - Eratosthenes C++ 实现的筛选（来自于 Soustrup C++ 编程原理一书）

Question

我已经尝试过我自己的算法实现，虽然它有效，但我确信它没有像算法应该的那样工作。这是代码：

#include "std_lib_facilities.h"

int main()
{
    vector<int> primes;
    int input; 

    cin >> input;
    
    for (int i =2;i<input;++i)
        primes.push_back(i);
    
    for (int j = 0; j<sqrt(input);++j)
        for (int i =j; i<primes.size();++i)
            if (i==j)
            {
            }
            else if (primes[i] % primes[j] == 0)
                primes.erase(primes.begin() + (i));
    
    cout << "Prime numbers are: "<<primes.size()<<endl;
    
    for (int j =0;j<primes.size();++j)
        cout <<primes[j]<<"; ";
}

虽然我找到了这个解决方案，但这不允许我从 2/3/5/7 的倍数开始，它只需要迭代 1 并且很难实现，因为素数向量大小总是在变化。

我不明白你如何“标记”非素数，然后你删除它们并保留素数，所以这就是 primes.erase 函数的推理。

如果我要列出在另一个向量中找到的非素数，并且在我找到所有非素数之后，从元素 1,2...n 的向量中减去非素数向量是否会更有效？在这种情况下，我们讨论的是本书迄今为止尚未描述的功能。

标签： c++