Che cosa causa un errore di segmentazione?

Question

Ho tentato di scrivere un programma che determinerà se un numero è primo o meno.L'ho basato sul Setaccio di Eratostene.Ad ogni modo, il mio programma funziona con numeri piccoli (15485863 funziona), ma se utilizzo numeri grandi (es.17485863) Ricevo un errore di segmentazione.Sto utilizzando long long senza segno e non credo di aver superato il loro valore massimo.Semplicemente non vedo cosa ho fatto di sbagliato.Grazie in anticipo per qualsiasi assistenza!

#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

Sulla Linea 24 hai: bool array[arrayLength]; Non puoi dichiarare un array sullo stack in questo modo.Il programma va in crash sulla linea 29.È necessario dichiararlo nell'heap utilizzando new/delete;

Qualcosa in questo senso (potrei avere una o due fughe di notizie lì dentro, ma hai capito);

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

Produzione

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

Si prega di notare che né lunga lunga, né l'uso di variabili per dimensionare gli array automatici sono parte di C ++ - sono estensioni fornite da gcc e non devono essere usati se la portabilità è un problema.

Per risolvere il problema, dimensionamento una matrice in questo modo:

 bool array[arrayLength];

causerà un overflow dello stack (e quindi un guasto seg) se il valore arrayLength è troppo grande. Utilizzare uno std :: vector, invece, ma essere consapevoli del fatto che la memoria non è una risorsa infinita.

Answer 3

E 'possibile per l'indice * greatestMult l'essere uguale a arrayLength, in modo da poter sovrascrivere l'ultimo elemento oltre la fine dell'array.

allocare anche matrici grandi in pila simili che possono causare un problema in base al sistema operativo. Alcuni sistemi si espanderà lo stack più di tanto, gli altri non saranno in grado di.