筛选N以内的素数（C语言代码）（埃氏筛选法）

解题思路:埃拉托斯特尼筛法 ，简称 埃氏筛 ，也称 素数筛 。
注意事项:用来找出一定范围内所有的素数。 所使用的原理是从2开始，将每个素数的各个倍数，标记成合数。 

一个素数的各个倍数，是一个差为此素数本身的等差数列。

此为这个筛法和试除法不同的关键之处，后者是以素数来测试每个待测数能否被整除。

 原理 给出要筛数值的范围n，找出 √n 以内的素数。 

先用2去筛，即把2留下，把2的倍数剔除掉；

再用下一个素数，也就是3筛，把3留下，把3的倍数剔除掉；

接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；不断重复下去。

参考代码:

#include<stdio.h>

#include<math.h>

int main(){

int n;

scanf("%d",&n);

int a[n+1];

for(int i=1;i<=n;i++){

a[i]=1;

}

a[1]=0;

for(int i=2;i<=sqrt(n);i++){

if(a[i]==1){

for(int j=2;j*i<=n;j++){

a[i*j]=0;

}

}

}

for(int i=1;i<=n;i++){

if(a[i]==1){

printf("%d\n",i);

}

}

return 0;

}