Ошибка времени выполнения (SIGSEGV) SPOJ Сито Эратосфена

Question

Ошибка времени выполнения (SIGSEGV) SPOJ Сито Эратосфена

Привет я получаю ошибку SIGSEGV для этой проблемы, не знаю, где это проблема: http://www.spoj.com/problems/PRIME1/
Я попытался решить эту проблему с помощью алгоритма решета Эратосфена, приведенного в Википедии.
Вот мой код, пожалуйста, помогите спасибо заранее.

int main()
{
int t;   // test cases

cin>>t;

while(t--)
{
long int m,n;
cin>>m>>n;if( 1 <= m <= n <= 1000000000 && n-m<=100000)
{
bool a[n];
for(long int i=2;i<=n;i++)
{
a[i]=true;  // set all to true
}
a[0]=false;
a[1]=false;
for( long int i=2;i*i<=n;i++)
{
if(a[i])
{
for( long int k=i*i;k<=n;k+=i)
{
a[k]=false;
}
}
}
for(long int i=m;i<=n;i++)
{
if(a[i])
cout<<i<<endl;         //Now all i such that a[i] is true are prime.
}
cout<<endl;
}
else
return -1;
}

return 0;
}

-4

algorithm c++math sieve-of-eratosthenes

Решение

Другие решения

Вы должны использовать GDB, чтобы узнать, что именно произошло. Есть много вещей не так с этим кодом.

Как указано в комментариях, для n достаточно большой ваш a[n] переполнит стек.
В первом и третьем у вас есть ошибка for петли; ты проверяешь a[n] но выделяется только до a[n-1], Все i <= n должно быть i < n
if( 1 <= m <= n <= 1000000000 && n-m<=100000) это, вероятно, не то, что вы хотели; для любого положительного целого числа ‘n’, (1 <= m <=n) будет правдой

4

Эта проблема была рассмотрена ранее на SO. Например, см. Сито Эратосфена при переполнении стека. Вы также можете прочитать этот блог, который описывает типичную реализацию C: С внедрением Сита из Эратосфена. Как указывалось выше, у вашего кода много проблем, и на самом деле так много, что вам нужно подумать о полной реорганизации. Пожалуйста, прочитайте связанные посты, чтобы узнать, как сделать это успешно.

0

Источник

Accepted Answer

Есть 3401 простых чисел ниже квадратного корня из 10⁹. Это все, что вам нужно, чтобы просеивать любой сегмент чисел ниже 10⁹ верхний предел.

Итак, во-первых, просейте сегмент от 2 до 31622. Сохраните полученные 3401 простое число в массиве.

Тогда для каждой пары чисел m <= n, m >= n - 100000 создать временный массив, охватывающий сегмент из m в n включите, и просейте это с теми простыми числами, которые Вы вычислили в первом шаге. Вы можете остановить каждое просеивание, когда квадрат простого числа выше заданного n:

for( i=0; primes[i]*primes[i] <= n; ++i)
{
....

Смотрите также мои посты про «офсетное сито» Эратосфена.

2