Segmentation Malfunction in a prime sieve

Question

when I run this program when entering a number greater than 46348, I get a segmentation error. For any values ​​below, the program works fine. 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 using a common architecture, the problem is that the calculation of calculating i*i full. The result cannot be stored in a 32-bit integer value. You can try adding cout << temp << endl; after this calculation. At the end he will print:

 2144523481 2146190929 2147117569 -2146737495 Segmentation fault 

In the future, you will want to run your code in the debugger. This makes it easier for you to find these things. I suspect CodeBlocks offers a graphical debugger. (Otherwise, be sure to compile with -ggdb and run your program with gdb )

---

Since you are on a 64-bit platform, you can use 64-bit unsigned integers to get a larger range. unsigned long long (C99, C ++ 0x) is a good way to ask for "the biggest you have, which is cheap enough." (Even if one long long can span two registers, as is the case with the 64-bit data type on IA32)

---

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

Answer 2

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

 int temp = i*i; 

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

 sieve[temp] = true; 

Having accessed an array with a negative number, you get a segmentation error.

---

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

Answer 3

This line: int temp = i * i; causes temp to overflow when I'm over 46348, forcing the sieve to look for the negative element. Segfault!

Replacing int with unsigned long long will allow you to make significant progress.