c++ - 素数筛分错

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) 是请求“你拥有的最大 int，它相当便宜”的好方法。 (即使一个 long long 可能跨越两个寄存器，就像 IA32 上的 64 位数据类型一样)

---

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