Quelle est la cause d'une erreur de segmentation?

Question

J'ai essayé d'écrire un programme qui permettra de déterminer si un nombre est premier ou non. Je l'ai basé sur de la Sieve d'Eratosthène. Quoi qu'il en soit, mon programme fonctionne pour un petit nombre (15485863 travaux), mais si j'utilise un grand nombre (ex. 17485863) Je reçois une erreur de segmentation. Je suis en utilisant languit unsigned long et ne pense pas avoir dépassé leur valeur maximale. Je ne vois pas ce que je l'ai fait mal. Nous vous remercions d'avance pour toute aide!

#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 vous avez: bool array[arrayLength]; Vous ne pouvez pas déclarer un tableau sur la pile comme celui-ci. Le programme se bloque sur la ligne 29. Vous devez déclarer sur le tas en utilisant les nouvelles / supprimer;

Quelque chose à cet effet (je peux avoir une fuite ou deux là-dedans, mais vous voyez l'idée);

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

Sortie

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

S'il vous plaît noter que ni longue, ni longue en utilisant des variables à la dimension des réseaux automatiques font partie de C ++ - ils sont des extensions fournies par gcc et ne doivent pas être utilisés si la portabilité est un problème.

Pour résoudre votre problème, le dimensionnement d'un tableau comme celui-ci:

 bool array[arrayLength];

provoque un débordement de pile (et donc un défaut de SEG) si la valeur arrayLength est trop grande. Utilisez un lieu std :: vecteur, mais sachez que la mémoire est une ressource infinie.

Answer 3

Il est possible pour l'indice * greatestMult soit égale à arrayLength, de sorte que vous pouvez remplacer le dernier élément après la fin du tableau.

allouer également de grands tableaux sur la pile comme cela peut poser un problème en fonction du système d'exploitation. Certains systèmes élargiront la pile beaucoup, d'autres ne seront pas en mesure de.