Segmentation Fault in prime number sieve

Question

when I run this program while inputting a number greater than 46348, I get a segmentation fault. For any values below it, the program works perfectly. I am using CodeBlocks 8.02 on Ubuntu 10.04 64-bit. The code is as follows:

int main()
{

    int number = 46348;
    vector<bool> sieve(number+1,false);
    vector<int> primes;
    sieve[0] = true;
    sieve[1] = true;

    for(int i = 2; i <= number; i++)
    {
        if(sieve[i]==false)
        {
            primes.push_back(i);
            int temp = i*i;
            while(temp <= number)
            {
                sieve[temp] = true;
                temp = temp + i;
            }
        }
    }

    for(int i = 0; i < primes.size(); i++)
        cout << primes[i] << " ";

    return 0;
}

Answer 1

Assuming you are on a common architecture, the problem is that the i*i calculation overflows. The result can not be stored in a signed 32 bit integer. You can try adding cout << temp << endl; after this calculation. In the end it will print:

2144523481
2146190929
2147117569
-2146737495
Segmentation fault

For the future, you will want to run your code in a debugger. It lets you spot these things more easily. I suspect CodeBlocks offers a graphical debugger. (Otherwise, make sure to compile with -ggdb and run your program with gdb)

---

Since you are on a 64 bit platform, you might want to use 64 bits unsigned integers to get a greater range. unsigned long long (C99, C++0x) is a good way to ask for "the biggest int you've got, that's reasonably cheap". (Even though one long long might span two registers, as is the case with a 64 bit datatype on IA32)

---

Alternatively, you can add a check to automatically verify that number < sqrt(numeric_limits<int>::max()) before entering the loop.