Question

C语言 用筛选法求500以内的素数并统计个数

需求高手指点...

Answer 1

/*用筛法求500以内的素数
*筛法是什么？
*就是说一个数如果除以n不为零，就是说这个数是n的倍数，那么这个数肯定不是
*素数，那么用一个n就可以把n的倍数都筛掉
*/
#include<stdio.h>
int main()
{
//初始化数组，也就是说，刚开始所有的数都是素数
int a[500]={0},i,j,count = 2;
a[0] = 1;a[1]=1;
//0和1肯定不是素数这个不用说了吧
for(i=2;i<500;i++)
{
//把i的n倍都筛掉。
for(j=2*i;j<500;j+=i)
{
if(a[j]!=1)
{
a[j] = 1;
count++;
}

}
}
for(i=1;i<=500;i++)
{
if(a[i] == 0)
{
printf("%d ",i);
}
}
//500个素数减去不是素数的个数就是素数的个数。
printf("count=",500-count);
return 0;
}

这个程序耗时比较多，如果你只是在学C语言遇到的问题，那么足够了，如果是学习算法，建议去网上找找更快的筛法。