Sieve of Eratosthenes

[declanmcerlane]

I'm working through Bjarne Stroustrup's [url=http://www.stroustrup.com/Programming/]latest book[/url] (aimed at teacher people C++ from the ground up). Enjoying it quite a lot. Haven't really encountered many problems with the exercises up until now; Chapter 04, to be precise.

Anyway, the point of this exercise is to use all the skills learnt from previous chapters (vectors, loops, conditional-statements etc) to generate a list of prime numbers using the "Sieve of Eratosthenes" algorithm.

Here's the source code:

// the "Sieve of Eratosthenes"

#include <iostream>
#include <vector>

using namespace std;

int main()
{
  // create empty vector to hold real numbers
  vector<int> real_numbers;

  // use "for" loop to populate vector
  for (int i = 2; i <= 100; ++i)
    real_numbers.push_back(i);

  // use "for" loop to work each element of vector
  for (int j = 0; j < real_numbers.size(); ++j)
  {
    // initialise first prime
    int prime = real_numbers[j];

    // use "for" loop to go through multiples of prime
    for (int multiple = 2; prime*prime <= 100; ++multiple)
      // remove current multiple of prime
      real_numbers.erase(real_numbers[multiple*prime]);
  }

  // use "for loop" to print remaining (prime) integers
  for (int k = 0; k < real_numbers.size(); ++k)
    cout << real_numbers[k] << " ";

  return 0;
}

When I try compile it with g++, however, I get the following error message.

g++ main.cpp -o main
main.cpp: In function ‘int main()’:
main.cpp:26: error: no matching function for call to ‘std::vector<int, std::allocator<int> >::erase(int&)’
/usr/include/c++/4.4/bits/vector.tcc:133: note: candidates are: __gnu_cxx::__normal_iterator<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::pointer, std::vector<_Tp, _Alloc> > std::vector<_Tp, _Alloc>::erase(__gnu_cxx::__normal_iterator<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::pointer, std::vector<_Tp, _Alloc> >) [with _Tp = int, _Alloc = std::allocator<int>]
/usr/include/c++/4.4/bits/vector.tcc:145: note: __gnu_cxx::__normal_iterator<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::pointer, std::vector<_Tp, _Alloc> > std::vector<_Tp, _Alloc>::erase(__gnu_cxx::__normal_iterator<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::pointer, std::vector<_Tp, _Alloc> >, __gnu_cxx::__normal_iterator<typename std::_Vector_base<_Tp, _Alloc>::_Tp_alloc_type::pointer, std::vector<_Tp, _Alloc> >) [with _Tp = int, _Alloc = std::allocator<int>]

the erase() member function belonging to vector seems to be the problem. The only member function I know of that removes elements is pop_back() but that only removes an element from the end of the vector - not really the desired effect.

Any comments/suggestions?

[Bazzy]

vector::erase takes iterator arguments. If you want to erase the n^th element from some vector, you need to call
some_vector.erase ( some_vector.begin() + n );
http://www.cplusplus.com/reference/stl/vector/erase/

[ne555]

That will be the Ulam sieve then.
Instead of directly erasing you could use a bool array that tells wich numbers should die. And you kill them from the greatest.

[declanmcerlane]

I never knew programming could be so violent!...I love it!

erase() still doesn't like me so I'll try

multiple*prime = 0;

and then print all the elements that aren't equal to 0.

I'll keep you posted!