【題目鏈接】

ybt 2040：【例5.7】篩選法找質數

【題目考點】

1. 普通篩法找質數（埃拉托色尼篩法）

基本思想：把從2到N的一組正整數從小到大按順序排列。從中依次刪除2的倍數、3的倍數、5的倍數，直到$\sqrt{N}$的倍數為止，剩余的即為2~N之間的所有質數。
普通篩法復雜度為:$O(nloglogn)$

為什么直到$\sqrt{N}$的倍數為止，以下是證明：

• 命題：對于整數n滿足$\sqrt{N}<n\le N$，n是質數，或n是合數時，存在一個整數a滿足$a\le \sqrt{N}$，a是n的因數。
• 證明：顯然n可以是質數。如果n是合數，使用反證法。
• 假設n是合數時，n的因數（除了1）都大于$\sqrt{N}$。由于n是合數，n至少有兩個不為1或n的因數，設為a，b，且存在等式$a?b?x=n$，其中x是某個正整數。
  有$a>\sqrt{N},b>\sqrt{N}?a?b>N\ge n$，即$a?b>n$
  根據$a?b?x=n$，有$a?b\le n$
  出現矛盾，因而假設不成立，原命題得證。

2. 線性篩（歐拉篩）

基本思想：讓每個合數只通過它最小的質因數被篩掉。

例：
8的最小質因數是2，那么讓合數8通過質數2被篩掉。
15的最小質因數是3，那么讓合數15通過質數3被篩掉。

普通篩法中，數字可能會被多次篩掉，線性篩中，每個數字只被篩掉一次。
線性篩法復雜度為:$O(n)$
線性篩的字面意思就是該算法的復雜度為線性的。

例：對于合數15
在普通篩法中：看質數3的倍數時，15被篩掉一次，看質數5的倍數時，15被篩掉一次。
在線性篩中： 15只會通過質數3被篩掉一次。

線性篩法中，維護一個質數數組prime[]。
算法如下：

• 每次循環觀察一個數字i
• 如果i是質數，加入質數數組
• 無論i是不是質數，都順序遍歷質數數組，取到的質數為prime[j]
  • 只要i不是prime[j]的倍數，那么prime[j]就是i*prime[j]的最小質因數。i*prime[j]這個合數通過prime[j]這個最小質因數被篩掉了。
  • 如果i是prime[j]的倍數，則跳出循環

原理解釋如下：

• 由于prime數組中的質數是遞增的，在遍歷prime數組的過程中，只要沒有遇到i是prime[j]的倍數的情況，那么prime[j]一定是i*prime[j]的最小質因數。當第一次遇到i是prime[j]的倍數的情況時，prime[j]仍然是i*prime[j]的最小質因數。
• 如果繼續看prime[j]后面第x個質數（x大于等于1），此時要判斷數字Y=i*prime[j+x]是否要被篩掉。由于prime[j+x] > prime[j]，i已經具有更小的質因數prime[j]，所以數字Y的最小質因數是prime[j]而不是prime[j+x]，所以Y這個數不應該在i為這個值時被篩掉，它應該在i為Y/prime[j]時被篩掉。

例：假設i是25。25不是2的倍數，那么2是2*25的最小質因數，25也不是3的倍數，那么3是3*25的最小質因數，25是5的倍數，5仍然是5*25的最小質因數。
25不是7的倍數，7不是7*25的最小質因數了。7*25=175被篩掉的時機是：當i循環到35時，175=35*5，5是175的最小質因數，175通過質數5被篩掉。

【題解代碼】

解法1：普通篩法（埃拉托色尼篩法）

#include<bits/stdc++.h> using namespace std; int main() {bool isPrime[1005] = {};//isPrime[i]:i是否是質數 int n;cin >> n;for(int i = 2; i <= n; ++i)//初值狀態下，把每個數字都標記為質數 isPrime[i] = true;//isPrime[0],與isPrime[1]都為false，0,1都不是質數 for(int i = 2; i <= int(sqrt(n)); ++i){if(isPrime[i]){for(int j = 2*i; j <= n; j += i)//如果一個數字是某質數的倍數，那么把它標記為合數 isPrime[j] = false;}}for(int i = 2; i <= n; ++i){if(isPrime[i])cout << i << endl;}return 0; }

解法2：線性篩（歐拉篩）

#include<bits/stdc++.h> using namespace std; int main() {bool isPrime[1005] = {};//isPrime[i]:i是否是質數 int n, prime[1005], psize = 0;//prime:質數數組 psize:prime數組長度 cin >> n;for(int i = 2; i <= n; ++i)//初值狀態下，把每個數字都標記為質數 isPrime[i] = true;//isPrime[0],與isPrime[1]都為false，0,1都不是質數 for(int i = 2; i <= n; ++i){if(isPrime[i])//如果i是質數 prime[++psize] = i;//將i填充到指數數組prime for(int j = 1; j <= psize && i*prime[j] <= n; ++j)//遍歷質數數組 {//篩去當前觀察的數i與某質數prime[j]的乘積isPrime[i*prime[j]] = false;//i*prime[j]這個數通過prime[j]篩掉 if(i%prime[j] == 0)break;}}for(int i = 2; i <= n; ++i){if(isPrime[i])cout << i << endl;}return 0; }

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 2040：【例5.7】筛选法找质数 (普通筛 线性筛)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。