Ошибка сегментации выделения массива С++ 11 Новичок

Я изучаю 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;
}

person David Williams    schedule 02.03.2013    source источник
comment
Ошибка сегментации обычно вызывается записью за пределы выделенной памяти. Вы должны использовать отладчик (или добавить операторы печати) для отслеживания хода выполнения вашей программы, чтобы выяснить, в какой момент это происходит.   -  person Oliver Charlesworth    schedule 02.03.2013
comment
Обратите внимание, что new не вернет NULL, если выделение не удалось (если не указано nothrow, чего здесь нет). Это вызовет исключение std::bad_alloc.   -  person Cornstalks    schedule 02.03.2013


Ответы (4)


Здесь у вас целочисленное переполнение:

        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, чтобы получить тот же эффект.

person NPE    schedule 02.03.2013

Когда вы запустите свою программу с помощью отладчика, вы увидите, что она терпит неудачу в

a[i * j] = 0;

i * j переполняется и становится отрицательным. Это отрицательное число меньше M, поэтому оно входит в цикл еще раз, а затем терпит неудачу при доступе к a[-2146737495].

person Olaf Dietsche    schedule 02.03.2013
comment
Будучи педантичным, я уверен, что вы знаете это, но технически это не обязательно должно быть -2146737495. - person chris; 02.03.2013
comment
@chris Это просто вырезано и вставлено из gdb. - person Olaf Dietsche; 02.03.2013

Ясно, проблема заключалась в объявлении M как int. Когда я объявляю i, M и j как long, это работает нормально.

person David Williams    schedule 02.03.2013
comment
Я бы не стал рассчитывать на то, что long сделает это. long имеет размер не менее 32 бит, и любая реализация, в которой он равен 32, вызовет переполнение. Однако long long составляет не менее 64 и официально является частью C++11. Тогда может возникнуть проблема со скоростью, если процессор 32-битный и много работает с 64-битными числами, но я даже близко не знал, насколько большая разница будет иметь значение, пока у меня не было времени. - person chris; 02.03.2013
comment
Как говорит NPE, если int равно 32 битам, то i * j переполнится и могут произойти плохие вещи (например, сбои). Сделать его long будет работать, если long будет иметь больше битов, что для вас и вашего компилятора возможно, long будет 64-битным, так что i * j больше не будет переполняться. - person Cornstalks; 02.03.2013

В любом достаточно современном C++ вы не получите нулевой указатель из new, если выделение не удалось, если только вы не используете не бросающее новое. Эта часть вашего кода не будет работать так, как вы ожидаете — вместо этого вам придется перехватывать std::bad_alloc, который может быть вызван вызовом new.

Вы также хотите объявить свои индексы массива как тип size_t.

person Timo Geusch    schedule 02.03.2013
comment
Не могли бы вы порекомендовать какие-либо учебные материалы по этому поводу? Я совершенно новичок в этом языке и еще не знаком с управлением памятью. - person David Williams; 02.03.2013
comment
@DavidWilliams, хорошая книга — это всегда хорошее начало. Имейте в виду, что современный C++ предназначен не столько для управления памятью, сколько для RAII, где вам не нужно ею управлять. - person chris; 02.03.2013