Was verursacht einen Segmentation Fault?

Question

Ich habe versucht, ein Programm zu schreiben, die bestimmen, ob eine Zahl eine Primzahl ist oder nicht. Ich habe es auf Basis des Sieb des Eratosthenes aus. Wie auch immer, funktioniert mein Programm für kleine Zahlen (15485863 Arbeit), aber wenn ich eine große Zahl verwenden (ex. 17485863) ich einen Segmentation Fault erhalten. Ich bin mit unsigned long longs und glaube nicht, dass ich ihren Maximalwert überschritten haben. Ich sehe einfach nicht, was ich falsch gemacht habe. Vielen Dank im Voraus für jede Hilfe!

#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

On Line 24 Sie haben: bool array[arrayLength]; Sie können ein Array auf dem Stapel wie folgt erklären. Das Programm stürzt auf Linie 29. Sie müssen dies auf dem Heap erklären, mit neuen / löschen;

Etwas zu diesem Zweck (I kann ein Leck oder zwei drin, aber Sie erhalten die Idee);

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

Ausgabe

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

Bitte beachten Sie, dass weder lange lange noch Variablen mit Hilfe der automatischen Arrays dimensionieren sind Teil der C ++ - sie sind Erweiterungen von gcc zur Verfügung gestellt und sollen nicht verwendet werden, wenn Portabilität ist ein Problem.

Ihr Problem adressieren, die Dimensionierung eines Arrays wie folgt:

 bool array[arrayLength];

wird einen Stapelüberlauf verursachen (und damit einen seg Fehler), wenn der ArrayLength Wert zu groß ist. Verwenden Sie einen std :: vector statt, aber bewusst sein, dass der Speicher nicht eine unendliche Ressource ist.

Answer 3

Es ist möglich, Index * greatestMult zu ArrayLength gleich sein, so dass Sie das letzte Element hinter dem Array Ende überschreiben können.

Auch große Arrays auf dem Stack wie die Zuweisung kann ein Problem verursachen, auf dem Betriebssystem abhängig. Einige Systeme werden die Stapel erweitern, dass viel, andere werden nicht in der Lage sein.