Sieve Of Eratosthenes Deleting list elements

Question

I have been working through the book by Stroustrup: http://www.amazon.com/Programming-Principles-Practice-Using-C/dp/0321543726 I am currently working on exercise 13 of chapter 4, which asks you to implement the Sieve of Eratosthenes algorithm to find the prime numbers between 1 and 100. http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes I am currently trying to delete the multiples of 2. I tried both the erase function and the remove_if(which causes odd segmentation errors). I am not looking for any implementation advice, just help with removing elements of vectors.

 #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
}

Any help is greatly appreciated! Thx!

Answer 1

To erase elements from STL containers, you'll need to use the erase-remove idiom: 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());
        ...
    }

To remove any value (just not multiples of 2), you can use function objects, or functors.

    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; }
    };

And to use it:

    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());

Answer 2

For efficiency reasons, you wouldn't usually delete the elements in the sieve of eratosthenes, but simply mark them as unused. You don't actually have to store the numbers 1 to 100 (or 1000, or whatever) in the vector. Instead, set every member of the vector to 1 (or 0) and then set it to the opposite to indicate that it's been crossed off. The numerical value of the element is simply its position in the array. To cross off every nth number, you have to scan through the array, counting up to n over and over, marking off those numbers.

To print out the values, you scan through the array and only print out the indices of the elements that are still 1.

Answer 3

In your code, since you are deleting the multiple of 2,3,5,7.... every time your vector size will change. I will suggest you to define a new variable int len = primer.size();//In this case it will be equal to Max-2 After that you can erase() function to update the vector.
#include #include #include using namespace std;

/*
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."<<"\n";
    int max = 100;
    for (int i = 2; i <= max; i += 1) { //creates a list of integers from 2  to 100.
        primer.push_back(i);
    }
    int len = primer.size();
    for (int i = 2; i < len; ) { //attempts to delete the multiplies of 2, excluding 2 itself.
         if(primer[i]%2==0) {
             primer.erase(primer.begin()+n);
             len = primer.size();
         }
         else
            i++;
}
 copy(primer.begin(), primer.end(), ostream_iterator<int>(cout, " "));//prints the elements of the vector

}