Ошибка сегментации в моем коде

Question

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

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

Answer 1

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

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

Answer 2

Конечно, вы будете выделять память, которая (нм) и вы используете простое число [n],

Answer 3

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

Answer 4

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

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