Segmentation Fault in my code
This is a code I submitted at sphere online judge for generating prime numbers but I'm getting a segmentation fault. The objective is to generate prime numbers between the given range m to n (with n > m). This is implemented using the Sieve of Eratosthenes algorithm. Please tell me where im going wrong. Thanks :)
#include <stdio.h>
#include <math开发者_如何学C.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;
}
c3
can go up to n
in the innermost loop, but you only may allocate less than n
slots in your array. In fact, even if you allocated n
slots, index n
would be one more than the number of slots you allocated. At worst, you'd just corrupt some memory past the end of the array and hopefully not trash the stack. At best, I guess you get a segfault. You probably want to change your X <= n
to X < n
or allocate one more element in your array. In fact, you probably should just allocate (n + 1) * sizeof(short)
bytes for your array.
Also, you never set t and you never never validate the user input. The latter may be okay if this is for a competition which would have constraints on input. Also, you never free the prime
array, so you have a memory leak.
Of course it will you are allocating a memory which is (n-m) & you are acessing prime[n] ,
Probably want to avoid this when prime is only 1 element long:
//set 1 and 0 as not prime
prime[0]=0;
prime[1]=0;
You malloc(n-m), but in the following loop you initialize prime[2..n]. n-m is at most 1E5, but n itself could be 1E9 (which is rather huge number). Your simple idea probably can not be implemented, because malloc(1E9) will probably fail. You need a smarter algorithm.
精彩评论