What's wrong with this algorithm implementation [Sieve of Erathosthene]

Question

I'm trying to implement the Sieve of Eratosthene in C++. However after several attempts at this I always get runtime errors. I'm thinking this has to do with the state of iterators being used get corrupted somewhere. I can't put my finger on it though. Here is my code:

    //Sieves all multiples of  the current sequence element
    bool multiple_sieve(std::list<int>& num_list)
    {
        std::list<int>::iterator list_iter(num_list.begin());
        std::list<int>::reverse_iterator last_element_iter(num_list.rbegin());

        for(std::list<int>::iterator elements_iter(++list_iter);
           elements_iter !=  num_list.end();)
        {
            if((*elements_iter % *list_iter == 0) &&
             (*elements_iter <= *last_element_iter) && (*list_iter != 1))
                num_list.erase(elements_iter);
            else ++elements_iter;
        }
        return true;
    }

    std::list<int>& prime_sieve(std::list<int>& num_list)
    {
        for(std::list<int>::iterator list_iter(num_list.begin());
          list_iter != num_list.end(); ++list_iter)
            multiple_sieve(num_list);
        return num_list;
    }

What I'm doing wrong? What's generating the runtime errors?

Update: When I run this in my tests I get an error with the message "list iterators are not compatible".

Answer 1

num_list.erase(elements_iter)

I don't think you should do this, this deletes the number from your list completely, you rather want to mark it as a non-prime.

If you really want to use STL for this instead of a bool array, better use std::bitset like in this implementation (well, there might also be better ones).

Answer 2

This line:

num_list.erase(elements_iter);

Is going to cause you problems since you are modifying the list while iterating it. You could do this to avoid that problem:

elements_iter = num_list.erase(elements_iter);

ETA: Removed stuff about erase() invalidating other iterators (looks like they are safe in this case) - just set elements_iter to the return value from erase() and you should be good to go.

Answer 3

I think I see one problem and it's std::list.erase(). erase() invalidates erased iterator only - all iterators to other parts are valid. After you erased it, you keep using it in for statement - "elements_iter != num_list.end()".

To solve you can use the fact that erase() returns iterator next after erased one or end if erased oiterator was last one. So replace line:

num_list.erase(elements_iter);

by

elements_iter = num_list.erase(elements_iter);

If you still have a problem I advise you to debug your algo under Visual Studio - it has degub version of STL, so in case of error debugger will stop on line causing problem.

Answer 4

I don't know why you're using a list here. It's easier to run sieve on vector and save primes in list.

std::list<int> primes(int MAXN){
  std::list<int> result;
  std::vector<bool> sieve(MAXN+1,true);
  for(int i=2;i<=MAXN;i++){
    if(sieve[i]==true){
      result.push_back(i);
      if((long long)i*i<=MAXN)  //prevent integer overflow
        for(int j=i*i;j<=MAXN;j+=i)
          sieve[j]=false;
    }
  }
  return result;
}

Answer 5

I've posted a more efficient sieve previously.

---

This works for me. Notable modifications from your code: use .erase(i++) otherwise the iterator gets invalidated, and start multiple_sieve from successive locations in the list rather than always from the start.

#include <iostream>
#include <list>

template<typename T, typename L>
void multiple_sieve(L &nums,
        const typename L::iterator &begin, const typename L::iterator &end) {
    T first = *begin;
    typename L::iterator i(begin);
    ++i;
    while (i != end)
        if (*i % first == 0) nums.erase(i++);
        else ++i;
}

template<typename T, typename L>
void prime_sieve(L &nums) {
    typename L::iterator end = nums.end();
    for (typename L::iterator i(nums.begin()); i != end; ++i)
        multiple_sieve<T, L>(nums, i, end);
}

int main(int argc, char **argv) {
    std::list<int> list;
    for (int i = 2; i < 1000; i++)
        list.push_back(i);
    prime_sieve<int, std::list<int> >(list);
    for (std::list<int>::iterator i(list.begin());
            i != list.end(); i++)
        std::cout << *i << std::endl;
}