HiHo一下 Week93 数论二·Eular质数筛法

HiHo

输入

一个数字 n

输出

一个数字m，为2~n中质数的个数

思路

1. 从2到n一个个用上次的Millar-Rabin方法判断。太慢
2. 普通筛法。有重复计算
3. 这次主角，Eular筛法 Eular Sieve Method
   我们先来看普通筛法中有哪些重复的计算，比如数字6，会在2的时候用2*3筛一次，在3的时候用3*2再筛一次。
   那么我们就会想到，规定对于每个数字n，只能筛一次，而且，这次筛法中是由n=m*p计算出的，p为n的最小质因子。
   我们在最外层循环里面对每个n进行判断，在普通筛法时，我们只用质数来筛，这里我们不管质数还是合数都拿来筛，但是我们的另一个因子，只有到目前为止已知的质数。
   讲得更明白点，普通晒法，对于$i\in [1,n]$，如果i为质数，那我们就$2i,3i,4i...pi$一直筛，而p是从1到[n/i]的所有数。
   而Eular筛法，，对于$i\in [1,n]$，无论i是质数还是合数，都用目前已知的质数来筛，就是筛去$2i,3i,5i,7i...pi$,这里p是小于i的最大质数（如果还没筛到p就发现i已经可以整除当前质数，那就跳出循环。只有这样才能保证筛的因子中有一个是最小质因子,因为$i*x$的最小因子一定是i的最小因子，到i可以整除当前质数，说明当前质数就是i的最小因子，再往后的话就不满足筛法分解中一定有最小质因子了。比如i=14，筛到$14*2$就行了，再往后筛$14*3$就会发现42这个数字没有被$21*2$筛而是被$14*3$筛了。）。这样，对于6，我们只有在i=3的时候才会筛到，用到了6的最小质因子2。同理，对于16，普通筛法有$2\times8,4\times 4,8\times 2$,Eular筛法中只会用$8\times 2$来筛，这里同样也是用到16的最小质因子。

代码

#include<iostream>
#include<vector>
using namespace std;
int main(){
    int n;
    cin >> n;
    std::vector<bool> isPrime(n+1,true);
    std::vector<int> primeList;
    int primeCount = 0;
    for(int i=2;i<=n;i++){
        if (isPrime[i]){            
            primeList[primeCount++] = i;
            primeList.push_back(i);
        }
        for(int j=0;j<primeCount;j++){
            if(i*primeList[j] > n) break;
            isPrime[i*primeList[j]] = false;
            if(i%primeList[j]==0) break;
        }
    }
    cout << primeCount;
    return 0;
}