C：埃拉托色尼筛不总是工作

Question

我正在做一个C程序，用厄拉多塞筛寻找质数

目前我有以下代码：

C

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class is_multiple_of {
    int m_div;
public:
    is_multiple_of(int div) : m_div(div) {}
    bool operator()(int n) { return ((n > m_div) && (0 == n % m_div)); }
};

int main ()
{
    vector<int> v;
    for (int i=2; i<=100; i++) v.push_back(i);

    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(2)), v.end() );
    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(3)), v.end() ); 
    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(5)), v.end() ); 
    v.erase( remove_if(v.begin(), v.end(), is_multiple_of(7)), v.end() ); 

    for (unsigned i=0; i<v.size(); ++i)
        cout << v[i] << " ";


    cout << endl << v.size();
    return 0;
}

这工作正常，即它说在1和100之间有25个素数（这是正确的）。但是，例如，如果我想知道前500个素数，它会说有118个，而实际上有95个。为了解决这个问题，我必须添加更多的倍数来删除，即v.erase（remove_if（v.begin（），v.end（），is_multiple_of（11）），v.end（））;，然后添加更多is_multiple_of（）。

有没有一种方法可以使它更有效，而不仅仅是让它去除以前发现的素数的更多倍数？

Answer 1

既然你想实现你的素数查找版本，那么下面的方法应该有效（我们使用的是500）

 int stopInt = static_cast<int>(sqrt(500));
 int j = 0;
 for (int i = 0; i < stopInt; ++i, ++j)
     v.erase(remove_if(v.begin(), v.end(), is_multiple_of(v[j])), v.end());

这里有一种替代方法，只需将项目移动到向量的末尾即可“标记”项目：

     vector<int>::iterator sMarked = v.end();
     int stopInt = static_cast<int>(sqrt(500));
     int j = 0;
     for (int i = 0; i < stopInt; ++i, ++j)
         sMarked = remove_if(v.begin(), sMarked, is_multiple_of(v[j]));
     v.erase(sMarked, v.end());

因此，我们通过跟踪< code>remove_if的返回值来不断标记元素。最后，我们执行一个简单的< code>vector::erase来删除多个。这应该比在循环中不断调用< code>v_erase更有效。