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

現給定任意正整數N(<10?5??)，請計算不超過N的滿足猜想的素數對的個數。
輸入格式:

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

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

20

輸出樣例:

4

代碼如下:

#include <iostream> using namespace std; const int N = 100010; int k; bool vis[N] = { false }; int isPrime[N];void initPrime() {k = 1;for (int i = 2; i < N; i++){if (!vis[i]){isPrime[k++] = i;for (int j = 2 * i; j < N; j += i)vis[j] = true;}} }int main() {initPrime();int n;cin >> n;int cnt = 0;for (int i = 2; i < k; i++){if (isPrime[i] > n) break;else if (isPrime[i] - isPrime[i - 1] == 2) cnt++;/*這里不要寫成isPrime[i+1]-isPrime[i]==2,因為我們if中是判斷isPrime[i],如果寫成這種，isPrime[i]可能沒超過n,但isPrime[i+1]超過了n，但是卻沒有break*/}cout << cnt << endl;return 0; }

總結

以上是生活随笔為你收集整理的[PAT乙级]1007 素数对猜想的全部內容，希望文章能夠幫你解決所遇到的問題。

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