问题标题: 酷町堂：质数筛是什么

课堂讲义给你：

埃氏筛法课后讲义（v2）

埃氏筛法

一、 埃氏筛法

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

二、 具体思想：

给出要筛数值的范围n，找出以内的素数。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去…。

三、 算法流程

排出从1~N的数列：1 2 3 4 5 6 7 8 9 10 11 12 ……

1不是素数，也不是合数，划去

2是素数，把N以内所有2的倍数划去

3是素数…… 重复划去过程直到sqrt(N)

四、 代码实现

找出1~10000范围内所有的质数。

#include<iostream>
#define MAXN 10005
using namespace std;
int a[MAXN];
int main()
{
      int n;
      cin>>n;
      a[1]=1;
      for(int i=2;i<=MAXN;i++){
          if(a[i]==0){
              for(int j=2*i;j<=MAXN;j+=i)
                  a[j]=1; 
          }
      }
      for(int i=1;i<=MAXN;i++){
          if(a[i]==0)
              cout<<i<<" ";
      }
      return 0;
}

五、 埃氏筛法的好处

（1）运用筛法找出一个区间内的质数，非常高效。

（2）运用筛法的思想，可以将程序代码简化。