埃拉托尼斯筛

• 前言
  在探究埃拉托尼斯筛之前，让我们先回顾一下线性筛选素数的方法。
  如果有数a为合数，那么一定存在素数x|a，且x^2<=a。
  代码如下：

  bool prime_judge(int x);
    for(int i=2;i*i<=x;i++) //这种写法相比于i<=sqrt(x)可以省去一些不必要的麻烦 
        if(x%i==0) return 0;
    return 1;
  

• 埃拉托尼斯筛的实现

  void fine_prime(int n,bool a[]){
    //引入的数组应是一个全局的，故不需要初始化，当然初始化也没问题
    //1为素数，0为合数
    a[0]=a[1]=1;//1和0是素数
    for(int i=2;i*i<=n;i++){//0和1不用讨论了 节省时间复杂度 
        if(a[i]==0)
            for(int j=i*2;j<=n;j+=i)
                a[j]=1;//直接筛去i的倍数 
    } 
  }