两种重要的素数筛法

原来以前一直写的素数筛是效率较低的埃氏筛法…其实还有一个复杂度为O(n)的素数筛法

1.埃氏筛法

基本思想就是一个素数的倍数肯定不是素数。那么我们从2开始推，将2的所有倍数标记为合数，接着往下找，若一个数没有被之前的数标记为合数，它就是一个新的素数。

const int maxn = 1e5 + 10;
int prime[maxn];

复杂度为O(nloglogn)

2.欧拉筛选法

const int maxn = 1024;
int prime[maxn],min_prime[maxn];
int Euler()
{
    int tot = 0;  //记录素数的个数
    for(int i=2;i<maxn;i++)
    {
      if(!min_prime[i])  //如果没有找到素因子，那么它本身就是素数
      {
        prime[tot++] = i;
        min_prime[i] = i;
      }
      for(int j=0;j<tot && prime[j] * i < maxn;j++)
      {

        min_prime[prime[j] * i] = prime[j];
        if(!(i % prime[j])) break;
      }
    }
    return tot;
}

复杂度为O(n)
对于i % prime[j] == 0 跳出的个人理解：
这意味着i中包含了prime[j]这个素因子，那么i prime[j+1] 其实可以被 某个数 prime[j]给筛去，所以这里的跳出是为了防止重复筛选。
另外，欧拉筛有一个好处是可以存每个数的最小素因子，对于素数，其最小素因子为零。这个性质可以用在一些解题上。