假设要求n以内的素数

筛法求素数是用一个大小为n的数组，作为标记数组，如果没被标记到则为素数。

开始均为未标记。

从2开始，2没被标记，将2存入一个存素数的地方，然后筛掉小于n的，2的所有倍数。然后是3，筛掉3的所有倍数，依此类推，直到n-1。

优化

上面的做法，同一个数可能会被筛掉多次，比如6会被3和2各筛一次。

为了提高效率，需要进行优化，使得每个数尽可能的被少筛，如果能一次最好。

考虑到任何合数都可以分解成若干个素数的乘积。在筛掉合数的过程中，最好的是让每个合数只被它最小的因子筛掉。

如24 18 都只被2筛掉

C++实现

vector<int> countPrimes(int n) {
    vector<bool> vis(n,false);
    vector<int> prime;

    for(int i=2;i<n;i++){
        if(!vis[i]) prime.push_back(i);
        for(int j=0;j<prime.size() && i*prime[j]<=n;j++){
            vis[i*prime[j]] = true;
            if(i%prime[j] == 0) break;	//优化
        }
    }
    return prime;
}

最外层循环每次循环，都能得到小于等于i的所有素数，当要求i+1内的素数时，只需判断i+1是否在之前被筛掉。

与此同时，将当前所有素数的i+1倍筛掉。

那后面出现的素数的i+1倍，设为m ，会怎么样呢？

  • 如果i+1是素数，m会被 i+1 筛掉
  • 如果i+1不是素数，则m 会被i+1的最小质因数（之前出现过的素数中的某一个）筛掉。

优化点：每个数都被它最小的因数筛掉

具体操作：如果循环到某个素数 prime[j] 是 i+1的倍数时，后面的素数的i+1倍 prime[j+1] * (i+1) 就不用筛了。

原因在于：后面素数的i+1倍一定会被 prime[j] （更小的一个数）筛掉，

$prime[j+1] * (i+1) = prime[j+1] * prime[j] * k$

$k = (i+1) / prime[j]$