Sieve of eratosthenes error

Question

I'm a newbie and I'm trying to learn C++. I'm reading Programming: Principles and Practice Using C++ and in chapter 4 there is an exercise to make a program to find primes using the sieve of Eratosthenes, however my program does not work and I am not sure why.

When I try to compile it I get the following warning:

warning C4018: '<' : signed/unsigned mismatch

Then when I run it, it crashes with the following debug error:

R6010 -abort() has been called

I looked at the code for a long time and couldn't find the error. I'm new so I don't know exactly what signed and unsigned means, but I've tried various inputs for x, like 10, 100, 1000.

the debugger shows:

"Unhandled exception at 0x759B2EEC in ConsoleApplication1.exe: Microsoft C++ exception: Range_error at memory location 0x0031F8C4."

Here is my code:

#include "../../std_lib_facilities.h"

int main()
{
    //program to find all prime numbers up to number input
    vector<int> list(2,0);          //to skip 0 and 1
    int x;
    cout << "Find all primes up to: ";
    cin >> x;
    for (int i = 0; i < (x-1); ++i){
        list.push_back(1);      //grow the vector and assigns 1
    }
    for (int i = 0; i < list.size(); ++i){
        if (list[i] == 1){      //find the next prime
            int c;
            c = i;
            while (c < list.size()){
                c += i;        //then finds all its multiples and,
                list[c] = 0;   //assign 0 to show they can't be primes
            }
        }
    }
    for (int i = 0; i < list.size(); ++i){  //goes through the vector
        if (list[i] == 1)              //write only primes
            cout << i << endl;
    }
}

What is the cause of the error?

Answer 1

The problem is likely here:

for (int i = 0; i < list.size(); ++i){
    if (list[i] == 1){
        int c;
        c = i;
        while (c < list.size()){
            c += i;        
            list[c] = 0;   //problem is here. On the last loops c+=i is too big           
        }
    }
}

The reason is because in the outermost for loop you end up with i == list.size() - 1. Now if c > 1 you will get c + i > list.size() then you try to access list[c+i] which is an index greater than the size of the list of primes. This is why when you run it for 1 it works but fails for any other larger number.

As for the compiler warning, that's because size() returns an unsigned size_t and your loop variable i is a signed int. When you then compare these this is what the compiler is complaining about. Change the loop to this:

for (size_t i = 0; i < list.size(); ++i){

and your compiler warning will go away.