素数筛法

1、埃氏筛法

根据质数的定义，能够被质数整除的数，肯定都是合数。

从小到大遍历每个数x，我们假设这个数是质数，把x的倍数都筛选掉，剩下的就是质数。

模拟筛法过程：

此算法用到了双重循环，但由于内层循环的步长为i，时间复杂度可看成O(nloglogn)。

for(int i=2; i<=n; i++) {
    if (isPrime[i]) {//不是合数，也就是质数
      primes.push_back(i);
      for(int j=2*i; j<=n ; j=j+i)
       	 isPrime[j] = false;
    }
  }

2、欧拉筛法

在筛法模拟里会看到存在大量的重复筛，比如6即被2筛掉、也被3筛掉， 如果每个合数都只被一个数筛掉，那么这个算法显然就是O(n)的算法，即线性筛法。

数学描述：每个数都只被它的最小质因子筛掉。

算法描述：

• 对每个数a，将a之前的质数乘以a筛为合数。
• 如果某个质数是a的因子，则停止（后面的不要筛了）

对于某个数a，假设已经找到m个质数：p、p1、...pm <= a， 计划将 a 和 这些质数的乘积都筛掉。

但如果a存在一个质因子，假设为px，即 a = px * t 那么对于px到pm之间的任何质数p，都有 a * p = px * (t * p) 也就是说后面肯定会有一个比a大的数b = (t*p)，也会筛掉 b * px = a * p

所以，这里就不需要筛这些质数（大于px的质数），可以直接跳过。

模拟筛法过程：

注意上面的8和9，只需要筛到其质因子乘以该数为止。

由于每个数都只有其最小质因子乘以某个a筛掉，所以这个算法为O(n)。

for(int i=2; i<=n; i++) {
    if(isPrime[i])
      primes.push_back(i);
      for(int j=0; j<primes.size(); j++) {
        int p = primes[j];
        if(i * p > n) break;
        isPrime[i * p] = false;
        if(i%p == 0) break;
      }
  }