c++ - Sieve Of Eratosthenes 删除列表元素

Question

我一直在研究 Stroustrup 的书: http://www.amazon.com/Programming-Principles-Practice-Using-C/dp/0321543726我目前正在做第 4 章的练习 13，它要求你实现 SieveEratosthenes 算法找到 1 到 100 之间的素数。 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes我目前正在尝试删除 2 的倍数。我尝试了删除函数和 remove_if(这会导致奇怪的段错误)。我不是在寻找任何实现建议，只是帮助删除 vector 元素。

 #include "std_lib_facilities.h"
#include <math.h>
#include <vector>
/*
This program attempts to find the prime numbers in the range of a value
using the Sieve of Eratosthenes algorithm.
*/
int main() {
    vector<int>primer;
    cout<<"This program calculates prime numbers up until a value max\n"
            "and prints these out."<<endl;
    int max = 100;
    for (int i = 2; i <= max; i += 1) { //creates a list of integers from 2 to 100.
        primer.push_back(i);
    }
    for (int n = 2; n < max; n += 2) { //attempts to delete the multiplies of 2, excluding 2 itself.
       primer.erase(?);
    }
     copy(primer.begin(), primer.end(), ostream_iterator<int>(cout, " "));//prints the elements of the vector
}

非常感谢任何帮助!谢谢!

Answer 1

要从 STL 容器中删除元素，您需要使用删除-删除习惯用法:http://en.wikipedia.org/wiki/Erase-remove_idiom

    bool is_even(int n) { return 0 == n % 2; }

    int main() 
    {
        ...
        v.erase(std::remove_if(v.begin(), v.end(), is_even), v.end());
        ...
    }

要删除任何值(只是不是 2 的倍数)，您可以使用函数对象或仿函数。

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

并使用它:

    v.erase(std::remove_if(v.begin(), v.end(), is_multiple_of(3)), v.end());
    v.erase(std::remove_if(v.begin(), v.end(), is_multiple_of(5)), v.end());