线性素数筛法(欧拉筛法)

概括

首先说一下欧拉筛法的时间复杂度为O(N)，这也是目前来说我知道的最快的素数筛法了，而且他是把素数都筛选了出来，跟埃式筛法不一样的是，每个素数都加进了素数表里面，埃式筛法紧紧是一个判断

思路

既然是O(N)的算法那么肯定是要线性走一遍2到maxn这个闭区间的，然后类似于埃式筛法如果当前的数没有被打上标记，那么加入到素数表里面，然后也类似于埃式筛法进行一波枚举，这里不同的是欧拉筛法是把当前的数与之前的素数表里面的数进行相乘而埃式筛法是直接把所有的2倍3倍4倍…都筛选了出来
然后最最重要的优化是
如果当前的i能够整除当前枚举的这个素数，那么就结束内层的枚举倍数算法这样能够保证每个合数都被筛选了一遍
因为要保证当前的素数不会被之后的筛选到！！！

代码

筛选前100个素数，使用欧拉筛法

#include <bits/stdc++.h>
using namespace std;
int bk[1000005],prime[1000005];
int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int cnt=0;
  for(int i=2;i<=1000000;i++)
  {
    if(!bk[i])
    prime[++cnt]=i;
    for(int j=1;j<=cnt&&i*prime[j]<=1000000;j++)
    {
      bk[i*prime[j]]=1;  
      if(i%prime[j]==0)  
      break;
    }
  }
  for(int i=1;i<=100;i++)
  cout<<prime[i]<<" ";
}