理解线性筛法

 

 1 #include<iostream>
 2 using namespace std;
 3 const long N = 200000;
 4 long prime[N] = {0}, num_prime = 0;
 5 int isNotPrime[N] = {1,1};
 6 int main() {
 7     for(long i = 2; i < N; ++i) {
 8         if(!isNotPrime[i])
 9             prime[num_prime++] = i;
10         for(long j = 0; j < num_prime && i*prime[j] < N; ++j) {
11             isNotPrime[i*prime[j]] = 1;
12             if(! (i % prime[j]) )//qwqwqwqwqwqwq 13                 break;
14         }
15     }
16     return 0;
17 }

 

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

注意到代码中赤黑色的记号了吗？

代码中其他的东西我都懂，这是个什么玩意？

本文撰写的目的就是帮助理解这个记号所标记的那一行~

 

除了线性筛法，我还接触过其他的筛法，当然都不是线性的，就算是线性筛法也不是绝对线性的。

正文开始前，先思考一个问题：为什么线性筛法是最优秀的？

 

答：对于单个数的筛除动作没有重复多次。

这就是线性筛法的“核心”了~

 

于是？

 

既然某些基于约数设计的算法无法简单地得到更有效的优化了，

从被筛数本身来考虑，说不定能另辟蹊径。

 

被筛数是合数，设为S。

于是这个合数有两个或以上的质因子，S = p（质因子） * K（K是某一个数）。

当然 p 、 K 的组合可以是多种多样的。

当S较大时， K是一个合数，于是K也可以拆分成 a*b的形式（a是质数， b嘛……不知道qwq），

S就可以写成这样：p * a * b。

a、b的大小有差别时， 某些规律就被呈现出来了：

 

一个合数与一个质数的乘积可以表示成一个更大的合数与一个更小的质数之积。

 

这个规律如何应用到质数的筛法上呢？

可以将这个规律的“唯一性”应用到质数的筛法上，

即每个较大合数都以这个规律中呈现的“唯一的最小质因子分解状态”被筛去。

 

现在再看代码中的“红色行”，

感觉仍然迷茫，代码的意思是：

 

质数会与之前的所有质数组合，筛除合数，

而合数与质数的组合却被限制，合数最多只能和自己的最小质因子及更小者组合？

为什么呢？

 

如果当前数是素数，显然之前数所筛除的数中都没有“当前数”这个质因子，与之前不会重复。

当前数是合数，被筛除的合数只会被以“最小态”筛除，一定不会重复，也一定不会被漏掉。

 

为什么不会被漏掉呢？<N的数的约数一定小于N。

为什么一定不会重复呢？

 

直观地理解：

设被筛的数是 S：p₁*p₂*p_3，p₁<p₂<p_3。

 既然保证当前数与质数的组合被限制， 就不会出现如下的情况 ： S以 p₃*p₂*p₁的形式删去。

更直观地，S的若干 质数*合数 的组合中， 只有其中唯一的一种， 即“最小态”会被生成。

于是线性筛法就这样很好地减少了操作的冗余度。

扫码关注我们

微信号：SRE实战

拒绝背锅 运筹帷幄