SPOJ PRIME1：即食；有没有办法避免动态数组？

Question

我阅读了埃拉托色尼筛分算法并尝试实现它，代码编译时没有任何错误，但我得到的是空白输出。这是代码：-

#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

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

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

int prime[542];

您还需要在代码中区分 n-the-number-of-primes 和 n-the-highest-prime。我建议保留 n 作为您希望查找的素数的数量，并使用 #define SIZE 542 作为数组的大小。确保在访问数组元素时使用 < SIZE 而不是 <= SIZE。

Answer 2

一件重要的事情：你不必打印 prime[i]（它是 1）但是 i. 这样你会得到更有趣的输出...

SPOJ PRIME1：即食；有没有办法避免动态数组？

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

c

primes

sieve-of-eratosthenes