0

这是我在 sphere online Judge 上提交的用于生成素数的代码，但我遇到了分段错误。目标是生成给定范围 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;
}
4

4 回答 4

3

c3可以n在最内层循环中上升，但您只能分配少于n数组中的插槽。事实上，即使您分配了n插槽，索引n也会比您分配的插槽数多一。在最坏的情况下，您只会破坏数组末尾的一些内存，并希望不会破坏堆栈。充其量，我猜你得到了一个段错误。您可能想要更改您的X <= ntoX < n或在您的数组中再分配一个元素。事实上，您可能应该只(n + 1) * sizeof(short)为您的数组分配字节。

此外，您永远不会设置 t 并且永远不会验证用户输入。如果这是对输入有限制的比赛，后者可能没问题。此外，您永远不会释放prime数组，因此存在内存泄漏。

于 2011-01-30T06:43:27.767 回答
1

当然，您将分配一个内存 (nm) 并且您正在访问 prime[n] ，

于 2011-01-30T06:43:38.233 回答
0

当素数只有 1 个元素时，可能希望避免这种情况：

//set 1 and 0 as not prime
        prime[0]=0;
        prime[1]=0;
于 2011-01-30T07:00:51.190 回答
0

你 malloc(nm)，但在下面的循环中你初始化 prime[2..n]。nm最多为 1E5，但n本身可能是 1E9（这是一个相当大的数字）。您的简单想法可能无法实现，因为 malloc(1E9) 可能会失败。你需要一个更智能的算法。

于 2011-01-30T09:41:16.680 回答