sintaxis - matriz en c++ codigo

Fallo de segmentación por asignación de matrices C++ 11 Newbie

Question

Estoy aprendiendo C ++ de Algoritmos en C ++ por Robert Sedgewick. En este momento estoy trabajando en el Tamiz de Eratóstenes con un límite superior especificado por el usuario en el primo más grande. Cuando ejecuto el código con un máximo de 46349, se ejecuta e imprime todos los números primos hasta 46349, sin embargo, cuando ejecuto el código con un máximo de 46350, se produce un error de segmentación. ¿Alguien puede ayudar a explicar por qué?

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

Código:

#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;
}

Answer 1

En cualquier C ++ razonablemente moderno, no obtendrá un puntero nulo de nuevo si la asignación falla a menos que use una nueva versión que no arroje. Esa parte de tu código no funcionará como lo esperas, tendrás que atrapar std::bad_alloc que podría ser emitido por la llamada a new lugar.

También quiere declarar sus índices de matriz como tipo size_t .

Answer 2

Usted tiene un desbordamiento de números enteros aquí:

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

46349 * 46349 no cabe en un int .

En mi máquina, cambiar el tipo de j a long hace posible ejecutar el programa para entradas más grandes:

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

Dependiendo de su compilador y arquitectura, puede que tenga que usar long long para obtener el mismo efecto.

Answer 3

Ya veo, el problema fue declarar M como un int. Cuando declaro i, M y j siempre, esto parece funcionar bien.

Answer 4

Cuando ejecuta su programa con un depurador, verá que falla en

a[i * j] = 0;

i * j desborda y se vuelve negativo. Este número negativo es menor que M , por eso ingresa al ciclo una vez más y luego falla al acceder a a[-2146737495] .