Что вызывает ошибку сегментации?

Question

Я пытался написать программу, которая будет определять, является ли число простым или нет. Я основал это на Сите Эратосфена. В любом случае, моя программа работает для небольших чисел (15485863 работает), но если я использую большие числа (например, 17485863), я получаю ошибку сегментации Я использую длинные беззнаковые лонги и не думаю, что превзошел их максимальное значение. Я просто не вижу, что я сделал неправильно. Заранее благодарю за любую помощь!

#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

Обратите внимание, что ни long, ни использование переменных для измерения автоматических массивов не являются частью C ++ - они являются расширениями, предоставляемыми gcc, и их не следует использовать, если переносимость является проблемой.

Чтобы решить вашу проблему, определите размер массива следующим образом:

 bool array[arrayLength];

вызовет переполнение стека (и, следовательно, ошибку сегмента), если значение arrayLength слишком велико. Вместо этого используйте std :: vector, но помните, что память не является бесконечным ресурсом.

Answer 2

В строке 24 у вас есть: bool array[arrayLength]; Вы не можете объявить массив в стеке следующим образом. Программа вылетает в строке 29. Вы должны объявить это в куче, используя new / delete;

Что-то на этот счет (у меня может быть утечка или две, но вы поняли);

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

выход

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 3

Индекс * greatMult может быть равен arrayLength, поэтому вы можете перезаписать последний элемент после конца массива.

Кроме того, размещение больших массивов в стеке может вызвать проблемы в зависимости от операционной системы. Некоторые системы будут расширять стек настолько, что другие не смогут.