¿Qué está causando un fallo de segmentación?

Question

He estado tratando de escribir un programa que va a determinar si un número es primo o no. He basado fuera de la criba de Eratóstenes. De todos modos, mi programa funciona para los números pequeños (15485863 obras), pero si uso un gran número (ej. 17485863) que recibe un fallo de segmentación. Estoy usando largos largos sin firmar y no creo que he superado su valor máximo. Yo no veo lo que he hecho mal. Gracias de antemano por cualquier ayuda!

#include <iostream>
#include <limits>

using namespace std;

bool soe (unsigned long long);

int main (void)
{
 unsigned long long x = 17485863;
 bool q = soe(x);

 cout << x << " is ";
 if(q)
  cout << "prime." << endl;
 else
  cout << "not prime." << endl;

 return 0;
    }

    bool soe(unsigned long long input)
    {
 unsigned long long arrayLength = input%2 + input/2;
 unsigned long long index = 2;
 unsigned long long greatestMult = 0;
 bool array[arrayLength];

 array[0] = true; //ignore true values in the array
 array[1] = true;
 do{
  array[index] = false;
 }while(++index < arrayLength);

 index = 2;

 do
 {
  if(input%index != 0)
  {
   greatestMult = input/index;
   while(index*greatestMult > arrayLength)
    greatestMult--;
   do
   {
    array[index*greatestMult] = true;
   }while(--greatestMult > 0);

   do
   {
    if(!array[index])
     break;
   }while(++index < arrayLength);

  }
  else
  {
   cout << endl << input << " is divisble by " << index << endl;
   return false;
  }
 }while(index < arrayLength);

 return true;
    }

Answer 1

en la línea 24 tiene: bool array[arrayLength]; No se puede declarar una matriz en la pila como este. El programa se cuelga en la línea 29. Es necesario declarar esta en el montón usando nuevos / delete;

Algo para este efecto (que puede tener una fuga o dos allí, pero usted consigue la idea);

 //Beginning on Line 28
 bool *array = new bool[arrayLength];

 array[0] = true; //ignore true values in the array
 array[1] = true;
 do{
  array[index] = false;
 }while(++index < arrayLength);

 index = 2;

 do
 {
  if(input%index != 0)
  {
   greatestMult = input/index;
   while(index*greatestMult > arrayLength)
    greatestMult--;
   do
   {
    array[index*greatestMult] = true;
   }while(--greatestMult > 0);

   do
   {
    if(!array[index])
     break;
   }while(++index < arrayLength);

  }
  else
  {
   cout << endl << input << " is divisble by " << index << endl;
   delete [] array;
   return false;
  }
 }while(index < arrayLength);

 delete [] array;
 return true;
    }

Salida

g++ -g test.cpp
gdb ./a.out
...clipped...
(gdb) run 
Starting program: /Users/nextraztus/a.out 
Reading symbols for shared libraries ++. done

17485863 is divisble by 3
17485863 is not prime.

Program exited normally.
(gdb) 

Answer 2

Tenga en cuenta que ni el tiempo ni el uso de variables de largo a las dimensiones de matrices automáticos son parte de C ++ - son extensiones proporcionadas por gcc y no se deben utilizar si la portabilidad es un problema.

Para hacer frente a su problema, el dimensionamiento de una serie como esta:

 bool array[arrayLength];

hará que un desbordamiento de pila (y por lo tanto un fallo seg) si el valor arrayLength es demasiado grande. Utilizar un std :: vector en su lugar, pero tenga en cuenta que la memoria no es un recurso infinito.

Answer 3

Es posible que el índice * greatestMult sea igual a arrayLength, por lo que puede sobrescribir el último elemento más allá del final de matriz.

También asignación de matrices grandes en la pila de esa puede causar un problema en función del sistema operativo. Algunos sistemas expanda la pila que mucho, otros no podrán.