Сегментация Неисправность в моем коде

Это код, который я представил в онлайн-судье сферы для генерации простых чисел, но у меня возникает ошибка сегментации. Целью является generate prime numbers между заданным диапазоном m до n (с n> m). Это реализовано с использованием алгоритма Sieve of Eratosthenes. Скажите, пожалуйста, где я ошибаюсь. Спасибо :)Сегментация Неисправность в моем коде

#include <stdio.h> 
#include <math.h> 

int main(){ 
    long int m,n,c1,c2,c3; 
    int t; 

    scanf("%d",&t); 
    while(t--) 
    { 
     scanf("%d %d",&m,&n); 


     //create prime list 
     short int *prime; 
     prime = (short int*)malloc((n-m)*sizeof(short int)); 

     //fill list with 0 - prime 
     for(c1 = 2; c1 <= n; c1++){ 
       prime[c1] = 1; 
     } 

     //set 1 and 0 as not prime 
     prime[0]=0; 
     prime[1]=0; 

     //find primes then eliminate their multiples (0 = prime, 1 = composite) 
     for(c2 = 2;c2 <= (int)sqrt(n)+1;c2++){ 
      if(prime[c2]){ 
       c1=c2; 
       for(c3 = 2*c1;c3 <= n; c3 = c3+c1){ 
        prime[c3] = 0; 
       } 
      } 
     } 

     //print primes 
     for(c1 = m; c1 <=n; c1++){ 
      if(prime[c1]) printf("%d\n",c1); 
     } 
    }  
    return 0; 
}

источник

2011-01-30 jaykumarark

Ну, где произошла ошибка сегментации? –

У вас есть информация о том, где находится segfault? Очень сложно найти одну ошибку в огромном блоке кода без какого-либо намека на то, где это может быть. – templatetypedef

использовать GDB и определить, где появляется segfault – shybovycha

c3 может доходить до n в внутреннем цикле, но только может выделять меньше n слотов в массиве. Фактически, даже если вы выделили n слоты, индекс n будет на один больше, чем количество выделенных слотов. В худшем случае вы просто испортили бы какую-то память за концом массива и, надеюсь, не сбросили бы стек. В лучшем случае, я думаю, вы получаете segfault. Вероятно, вы захотите изменить свой X <= n на X < n или выделить еще один элемент в своем массиве. Фактически, вы, вероятно, должны просто выделить (n + 1) * sizeof(short) байтов для вашего массива.

Кроме того, вы никогда не устанавливаете t, и вы никогда не проверяете ввод пользователя. Последнее может быть в порядке, если это для конкуренции, которая имела бы ограничения на ввод. Кроме того, вы никогда не освобождаете массив prime, поэтому у вас есть утечка памяти.

источник

2011-01-30 06:43:27 siride

Ну, сервер собирается скомпилировать программу, поэтому я предположил, что t, m и n будут в пределах, указанных в разделе пользовательского ввода. Нужно ли проверять их? – jaykumarark

@jaymumarark: Я пропустил, где t был извлечен из пользовательского ввода. Таким образом, m, n и t могут быть непроверены, если предположить, что судьи сказали, что они не будут давать вам мусор. – siride

Конечно, вы выделяете память, которая (нм) & вы acessing простого [п],

источник

2011-01-30 06:43:38

Вероятно, хочет, чтобы избежать этого, когда премьер только один элемент длиной:

//set 1 and 0 as not prime 
     prime[0]=0; 
     prime[1]=0;

источник

2011-01-30 07:00:51

Вы malloc (nm), но в следующем цикле вы инициализируете prime [2..n]. n-m не более 1E5, но n сам может быть 1E9 (это довольно большое количество). Ваша простая идея, вероятно, не может быть реализована, потому что malloc (1E9), вероятно, не удастся. Вам нужен более разумный алгоритм.

источник

2011-01-30 09:41:16 Dialecticus

Сегментация Неисправность в моем коде

ответ

Смежные вопросы