CODEWITHSUNDEEP
c++linuxsegmentation-fault
rEgonicS
rEgonicS

Reputation: 211

Segmentation Fault in prime number sieve

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

Upvotes: 4

Views: 818

Answers (3)

Magnus Hoff
Magnus Hoff

Reputation: 22089

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.

Upvotes: 7

small_duck
small_duck

Reputation: 3094

This line: int temp = i*i; causes temp to overflow when i is bigger than 46348, causing the sieve to look for a negative element. Segfault!

Replacing int by unsigned long long will allow you to go much further.

Upvotes: 1

Felix Kling
Felix Kling

Reputation: 816880

temp is a 32bit signed integer. In this line:

int temp = i*i;

it computes 46348*46348 = +2,148,137,104 (maximum value for an signed integer is +2,147,483,647) which creates an overflow (it becomes a negative number) and later you try to access the array with this result:

sieve[temp] = true;

By accessing the array with a negative number you get the segmentation fault.

(You could change it to unsigned int (maximum value +4,294,967,295)

Upvotes: 1

Related Questions