素数筛分段故障

Question

当我输入一个大于46348的数字运行这个程序时,我得到一个分段错误.对于它下面的任何值,该程序完美地运行.我在Ubuntu 10.04 64位上使用CodeBlocks 8.02.代码如下:

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

假设您使用的是通用架构,问题是i*i计算溢出.结果不能存储在带符号的32位整数中.您可以尝试cout << temp << endl;在此计算后添加.最后它将打印:

2144523481
2146190929
2147117569
-2146737495
Segmentation fault

对于将来,您需要在调试器中运行代码.它可以让您更轻松地发现这些东西.我怀疑CodeBlocks提供了一个图形调试器.(否则,请确保编译-ggdb并运行您的程序gdb)

由于您使用的是64位平台,因此您可能需要使用64位无符号整数来获得更大的范围.unsigned long long(C99,C++ 0x)是一个很好的方式来询问"你得到的最大的东西,这是相当便宜的".(即使有人long long可能跨越两个寄存器,就像IA32上的64位数据类型一样)

或者,您可以添加检查以number < sqrt(numeric_limits<int>::max())在进入循环之前自动验证.