c - SPOJ PRIME1 : RTE; Is there a method to avoid dynamic array?

Question

我阅读了有关 Eratosthenes 算法的 Sieve 算法并尝试实现它，代码正在编译时没有任何错误，但我得到的是空白输出。这是代码:-

#include <stdio.h>
#include <stdlib.h>
#define limit 100000
int main()
{
int prime[limit];
int i,j,t;
int n,m;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
for(i=0;i<=n;i++)
{
    prime[i]=1;
}
prime[0]=0;
prime[1]=0;
for(i=2;i<=n;i++)
{
    if(prime[i]==1)
    {    for(j=2;i*j<=n;j++)
              prime[i*j]=0;
    }
}
for(i=m;i<=n;i++)
{
    if(prime[i]!=0)
        printf("%d\n",i);
}
}


return 0;
}

Answer 1

问题在于您的筛阵列的大小:它必须足够大以拉伸(stretch)到您希望处理的最高数量，而不是您希望找到的项目数量。

您的实现适用于查找 100 以内的素数，而不是前 100 个素数。由于质数100是541，所以需要将size改为542:

int prime[542];

你还需要区分n -素数和n -代码中的最高素数。我建议保留 n对于您希望找到的素数计数，并使用 #define SIZE 542对于数组的大小。确保使用 < SIZE而不是 <= SIZE访问数组元素时。