5.质数筛法-开发者社区

一. 什么是质数筛法?

质数筛法就是给定一个范围, 如何从中筛选出所有质数?
比如这里给定一个数nnn要求筛选[1,n][1, n][1,n]范围内的所有质数, 并按顺序输出

接下来我想给大家介绍三种质数筛选的方法

朴素筛法
埃拉托色尼筛法
欧拉筛法

这三个筛选法越来越接近神的!!!

二. 朴素筛法

不看名字起的很朴素, 方法也是非常朴素, 就是从111遍历到nnn, 依次判断是否为质数

vector<int>primes;// 收纳质数// 由于可以肯定1不是质数, 所以直接从2开始遍历for(inti=2;i<=n;i++){if(isPrimeNum(i))primes.push_back(i);// 如果是质数就收纳进来}

我们知道一个质数xxx需要满足其因子只含111和xxx本身, 那我们就可以写出这样的方法来判断是否为质数

// 判断是否为质数boolisPrimeNum(intx){if(x<=1)returnfalse;for(inti=2;i<=x-1;i++){if(x%i==0)returnfalse;// 含其他因子}// 遍历完[2, x - 1]内的所有数, 发现不存在x的因子, 则判断是质数returntrue;}

只需要确认[2,x−1][2, x - 1][2,x−1]都不存在xxx的因子, 则可判断xxx是质数
算法时间复杂度为 :O(n2)O(n ^ 2)O(n2)

那这段程序有没有优化空间呢?当然是有的, 比如一个数xxx其除本身之外最大的因子就是x2\frac{x}{2}2x, 所以根本不需要遍历[2,x−1][2, x - 1][2,x−1]的全部数, 只需要遍历[2,x2][2, \frac{x}{2}][2,2x]即可, 这样确实可以大大节省算法时间, 但其时间复杂度依旧是O(n2)O(n ^ 2)O(n2)

那这个朴素筛法是不是没有优化空间了呢?🤨
其实我们小学就学过一个知识点因数的成对性, 比如对于100100100来说
1×100=1002×50=1004×25=1005×20=10010×10=100 \begin{aligned} &1 \times 100 = 100 \\ &2 \times 50 = 100 \\ &4 \times 25 = 100 \\ &5 \times 20 = 100 \\ &10 \times 10 = 100 \\ \end{aligned}1×100=1002×50=1004×25=1005×20=10010×10=100
我们可以发现构成100100100的因子都是成对出现的, 而且xxx的一对因子a,ba, ba,b, 一定满足
a≤x≤ba \le \sqrt{x} \le ba≤x≤b
这里我们可以简单证明一下
∀x∈N,0≤a≤bif:a×b=x ⟺ a×b=xbecause a≤b,therefore a2≤a×b≤b2 ⟺ a≤x≤b \begin{aligned} &\forall x \in N, 0 \le a \le b\\ &if : a \times b = x \iff \sqrt{a \times b} = \sqrt{x}\\ &because \ a \le b, therefore \ \sqrt{a ^ 2} \le \sqrt{a \times b} \le \sqrt{b ^ 2} \iff\\ &a \le \sqrt{x} \le b \end{aligned}∀x∈N,0≤a≤bif:a×b=x⟺a×b=xbecausea≤b,thereforea2≤a×b≤b2⟺a≤x≤b
所以对于一个数xxx, 我们只需要判断[2,x][2, \sqrt{x}][2,x]范围内没有xxx的因子, 那[2,x−1][2, x - 1][2,x−1]范围内也不可能有xxx的因子, 根据这个条件, 上述判断算法就可以优化为

// 判断是否为质数boolisPrimeNum(intx){if(x<=1)returnfalse;for(inti=2;i<=sqrt(x);i++){if(x%i==0)returnfalse;// 含其他因子}// 遍历完[2, x - 1]内的所有数, 发现不存在x的因子, 则判断是质数returntrue;}

整体朴素筛选法时间复杂度最终可以优化为O(n32)O(n ^{\frac{3}{2}})O(n23)

三. 埃拉托色尼筛法(埃氏筛法)

埃拉托色尼之后的质数筛选法就开始造神了, 在开始学埃氏筛法之前, 我们首先要掌握一个定理 ——唯一分解定理

任何一个大于111的正整数nnn，都可以唯一表示为有限个质数的乘积

我们可以在此基础上得到一个小的推论, 假如xxx为一个质数, 那么它的mmm倍就一定是一个合数, 这里的mmm是一个大于111正整数

如果mmm是质数, 那正好满足唯一分解定理,x×mx \times mx×m就是一个合数
如果mmm是一个合数, 那mmm还可以根据唯一分解定理拆成若干质数的积, 所以x×mx \times mx×m依旧是合数

这里我为什么肯定x×mx \times mx×m是一个合数, 因为它除了111和它本身意外, 已经包含了mmm这个因子

根据这个定理, 我们就拥有了一个筛选质数全新的方法, 每筛选出一个质数xxx, 就把含xxx这个因数的合数全部排除掉

vector<int>primes;// 收纳质数vector<int>isPrime(n+1);// 标记当前数字是质数还是合数, 1表示质数, 0表示合数isPrime.assign(isPrime.size(),1);// 初始化全为质数// 从2开始遍历, 将质数放入质数数组for(inti=2;i<=n;i++){if(isPrime[i]){// 如果i是质数primes.push_back(i);// 直接将其装入质数数组// 然后将由该质数i的倍数全部筛掉, 因为i的若干倍一定是合数for(intj=i*2;j<=n;j+=i){isPrime[j]=0;// 标记为合数}}}

算法时间复杂度 :O(nloglogn)O(nloglogn)O(nloglogn)
这个算法的时间复杂度算起来比较复杂, 有能力的小伙伴可以去尝试一下🙂

四. 欧拉筛法(线性筛法)

接下来, 真神登场, 根据名字我们也可以知道, 这个算法的时间复杂度是线性的, 也就是O(n)O(n)O(n)
首先我们不谈这个算法为什么更优, 而是谈谈埃氏筛法还有什么弊端, 仔细观察我们会发现, 我们每选中一个质数, 就把它后面的合数筛掉, 看似完美, 实则冗余

比如,15=3×515 = 3 \times 515=3×5, 同时,15=5×315 = 5 \times 315=5×3, 所以当我们选中质数333时,151515会被筛一次, 当我们选中555时,151515又会被筛一次, 不止是151515, 只要一个数可以拆为多个不同质因数的积, 就会被筛多次, 这样就会出现非常多的冗余操作, 从而增加我们的时间复杂度

根据唯一分解定理, 既然每一个合数都可以由若干质因子乘积唯一表示, 那保证这个合数只被其最小的质因子筛掉不就行了吗?
2×2=42×3=62×2×2=83×3=92×5=102×2×3=122×7=143×5=152×2×2×2=16⋯ \begin{aligned} &2 \times 2 = 4\\ &2 \times 3 = 6\\ &2 \times 2 \times 2 = 8\\ &3 \times 3 = 9 \\ &2 \times 5 = 10\\ &2 \times 2 \times 3 = 12\\ &2 \times 7 = 14\\ &3 \times 5 = 15\\ &2 \times 2 \times 2 \times 2 = 16\\ &\cdots \end{aligned}2×2=42×3=62×2×2=83×3=92×5=102×2×3=122×7=143×5=152×2×2×2=16⋯
比如4,6,8,10,12,14,164, 6, 8, 10, 12, 14, 164,6,8,10,12,14,16就只被222筛掉,9,159, 159,15就只被333筛掉

vector<int>primes;// 收纳质数vector<int>isPrime(n+1);// 标识是否为质数isPrime.assign(isPrime.size(),1);// 初始化全为质数for(inti=2;i<=n;i++){if(isPrime[i]){primes.push_back(i);// 将其装入质数数组}// 遍历所有数i的质数倍, 然后将其后面的合数直接筛掉, 而且保证当前被筛掉的合数只被其最小质因子筛掉, 否则直接结束for(intj=0;j<primes.size();j++){if(i*primes[j]>n)break;// 如果超出筛选范围isPrime[i*primes[j]]=0;// 否则直接将其标记为合数// 而且保证其只被最小的质因子筛掉if(i%primes[j]==0)break;}}

这段代码可能有些地方让人难以理解, 这里我详细说明一下, 大体思路如下

从222遍历到nnn, 如果遇到质数就收纳
将每一个遍历的数i×primes[j](质数)i \times primes[j](质数)i×primes[j](质数), 就可以得到一个合数
如果i×primes[j]>ni \times primes[j] > ni×primes[j]>n就直接结束, 因为我们只要求筛掉[2,n][2, n][2,n]范围内的合数
如果得到的合数i×primes[j]i \times primes[j]i×primes[j]在范围内, 就直接筛掉即可
如果i mod primes[j]==0i \ mod \ primes[j] == 0imodprimes[j]==0, 说明当前p=primes[j]p = primes[j]p=primes[j]是iii的最小质因子, 那么ppp自然也是i×pi \times pi×p的最小质因子, 如果继续遍历到更大的质数p′p'p′,i×p′i \times p'i×p′的最小质因子依然也是ppp, 所以为了不重复筛选, 这里就可以直接退出了