управление памятью — ошибка сегментирования массива C ++ 11 Новичок

Question

управление памятью — ошибка сегментирования массива C ++ 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;
}

1

c++memory-management segmentation-fault sieve-of-eratosthenes

Решение

Другие решения

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

a[i * j] = 0;

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

3

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

1

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

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

1

Источник

Accepted Answer

У вас есть целочисленное переполнение здесь:

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

5