[关闭]
@lunar 2016-04-14T16:10:20.000000Z 字数 1125 阅读 1351

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为质数,那我们就一直筛,而p是从1到[n/i]的所有数。
    而Eular筛法,,对于,无论i是质数还是合数,都用目前已知的质数来筛,就是筛去,这里p是小于i的最大质数(如果还没筛到p就发现i已经可以整除当前质数,那就跳出循环。只有这样才能保证筛的因子中有一个是最小质因子,因为的最小因子一定是i的最小因子,到i可以整除当前质数,说明当前质数就是i的最小因子,再往后的话就不满足筛法分解中一定有最小质因子了。比如i=14,筛到就行了,再往后筛就会发现42这个数字没有被筛而是被筛了。)。这样,对于6,我们只有在i=3的时候才会筛到,用到了6的最小质因子2。同理,对于16,普通筛法有,Eular筛法中只会用来筛,这里同样也是用到16的最小质因子。

代码

  1. #include<iostream>
  2. #include<vector>
  3. using namespace std;
  4. int main(){
  5. int n;
  6. cin >> n;
  7. std::vector<bool> isPrime(n+1,true);
  8. std::vector<int> primeList;
  9. int primeCount = 0;
  10. for(int i=2;i<=n;i++){
  11. if (isPrime[i]){
  12. primeList[primeCount++] = i;
  13. primeList.push_back(i);
  14. }
  15. for(int j=0;j<primeCount;j++){
  16. if(i*primeList[j] > n) break;
  17. isPrime[i*primeList[j]] = false;
  18. if(i%primeList[j]==0) break;
  19. }
  20. }
  21. cout << primeCount;
  22. return 0;
  23. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注