1

Robert Sedgewick の Algorithms in C++ から C++ を学んでいます。現在、ユーザーが指定した最大素数の上限を使用して、エラトステネスのふるいに取り組んでいます。最大 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。

私のマシンでは、 の型をjtoに変更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からnullポインターが返されることはありません。コードのその部分は、期待どおりに機能しません。代わりにstd::bad_alloc、への呼び出しから発生する可能性のある部分をキャッチする必要がありますnew。

また、配列インデックスをタイプとして宣言する必要がありますsize_t。

于 2013-03-02T17:01:07.057 に答える