埃氏筛法求素数（C语言）

素数（C语言）"/>

埃氏筛法求素数（C语言）

问题要求：

用埃氏筛法求100000以内的素数，并输出总个数。

知识简介：

埃氏筛法，全名埃拉托斯特尼筛法，也叫爱氏筛法，是一种由希腊数学家埃拉托斯特尼所提出的一种简单检定素数的算法。
要得到 自然数 n 以内的全部素数，必须把 不大于根号 n 的所有素数的倍数剔除，剩下的就是素数。

全部代码：

#include <stdio.h>
#include <math.h>int main(){int prime[100001];int count=0;for(int i=0;i<=100000;i++){prime[i]=1;                            //初始化所有的数为素数}for(int i=2;i<=sqrt(100000);i++){               //从第一个素数2开始筛选if(prime[i]){                          //如果是素数for(int j=i*i;j<=100000;j+=i){          //则剔除掉它的倍数prime[j]=0;}}}for(int i=2;i<=100000;i++){if(prime[i]){count++;printf("%6d ",i);if(count%5==0)putchar('\n');}}printf("count=%d",count);return 0;
}