立志用更少的代碼做更高效的表達

---

Pat乙級最優化代碼+題解+分析匯總——>傳送門

---

讓我們定義d_n
?? 為：d_n=p_n+1??p_n，其中p_i是第i個素數。顯然有d₁=1，且對于n>1有d?_n是偶數。“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”。

現給定任意正整數N(<10₅)，請計算不超過N的滿足猜想的素數對的個數。

輸入格式:
輸入在一行給出正整數N。

輸出格式:
在一行中輸出不超過N的滿足猜想的素數對的個數。

輸入樣例:
20
輸出樣例:
4

---

解題思路

本題的核心考點為：篩選法求某一區間的素數。

說明：篩選法可求某一數字區間的所有數字是否為素數， 且時間復雜度極低。

應用場景： 打表。 事先定義數組，利用篩選法，求得該數組所有數字下標是否為素數。 為接下來的判斷操作做準備。

理解篩選法后， 本體就很好做了， 只需要判斷是否差值為2即可。

---

代碼展示

#include<iostream> #include<cmath> #define Max 100005 using namespace std; int a[Max];void Sifting() { //篩選法求素數a[1] = a[0] = 1;for(int i = 2; i < sqrt(Max); i++) if(a[i] == 0) for(int j = i*2; j <= 100005; j+=i) a[j] = 1; }int main() {Sifting();int n; cin>>n;//sum記錄上一個質數，與這個質數比較是否差值為2; num代表差值為2素數對的個數 int sum = 3, num = 0; for(int i = 0; i <= n; i++) if(a[i] == 0) {if(i-sum==2) num++; sum = i;}cout << num << endl; return 0; }

---

每日一句

惟正己可以化人，唯盡己可以服人。

總結

以上是生活随笔為你收集整理的满分最优解法：1007 素数对猜想 (20分)的全部內容，希望文章能夠幫你解決所遇到的問題。

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