1

我正在从 Robert Sedgewick 的 C++ 算法中学习 C++。现在，我正在研究 Eratosthenes 筛，用户指定了最大素数的上限。当我以最大 46349 运行代码时，它会运行并打印出最多 46349 的所有素数，但是当我以最大 46350 运行代码时，会发生分段错误。有人可以帮忙解释为什么吗？

./sieve.exe 46349
 2 3 5 7 11 13 17 19 23 29 31 ...

./sieve.exe 46350
 Segmentation fault: 11

代码：

#include<iostream>

using namespace std;

static const int N = 1000;

int main(int argc, char *argv[]) {
    int i, M;

    //parse argument as integer
    if( argv[1] ) {
        M = atoi(argv[1]);
    }

    if( not M ) {
        M = N;
    }

    //allocate memory to the array
    int *a = new int[M];

    //are we out of memory?
    if( a == 0 ) {
        cout << "Out of memory" << endl;
        return 0;
    }

    // set every number to be prime
    for( i = 2; i < M; i++) {
        a[i] = 1;
    }

    for( i = 2; i < M; i++ ) {
        //if i is prime
        if( a[i] ) {
            //mark its multiples as non-prime
            for( int j = i; j * i < M; j++ ) {
                a[i * j] = 0;
            }
        }
    }

    for( i = 2; i < M; i++ ) {
        if( a[i] ) {
            cout << " " << i;
        }    
    }
    cout << endl;

    return 0;
}
4

4 回答 4

5

你在这里有整数溢出：

        for( int j = i; j * i < M; j++ ) {
            a[i * j] = 0;
        }

46349 * 46349不适合int.

在我的机器上，将类型更改为j可以long为更大的输入运行程序：

    for( long j = i; j * i < M; j++ ) {

根据您的编译器和架构，您可能必须使用long long才能获得相同的效果。

于 2013-03-02T17:01:41.657 回答
3

当您使用调试器运行程序时，您会看到它在

a[i * j] = 0;

i * j溢出并变为负数。这个负数小于M，这就是它再次进入循环然后访问失败的原因a[-2146737495]。

于 2013-03-02T17:05:20.903 回答
1

我明白了，问题在于将 M 声明为 int。当我声明 i,M 和 j 时，这似乎工作正常。

于 2013-03-02T17:01:06.200 回答
1

在任何相当现代的 C++ 中，如果分配失败，您将不会从 new 返回空指针，除非您使用非抛出 new。您的代码的那部分不会像您期望的那样工作 - 您必须捕获std::bad_alloc可能从调用中发出的内容new。

您还想将数组索引声明为 type size_t。

于 2013-03-02T17:01:07.057 回答