題目

讓我們定義d?_n 為：d_?n?? =p_?n+1?? ?p_?n?? ，其中p_i?? 是第i個素數。顯然有d_?1?? =1，且對于n>1有d_?n?? 是偶數。“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”。
現給定任意正整數N(<10?⁵?? )，請計算不超過N的滿足猜想的素數對的個數。

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

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

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

C++實現

#include <iostream> #include <cstring> using namespace std; bool is_pnum(int num) {for (int i = 2; i*i <= num; ++i) {if (num%i==0) return false;}return true; } int main() {int n;cin>>n;int temp=0;for (int i = 5; i <= n; ++i) {if (is_pnum(i)&&is_pnum(i-2)) temp++;}cout<<temp<<endl;return 0; }

python實現

import mathdef is_prime(n):if n%3==0 and n!=3:return Falsefor i in range(3,int(math.sqrt(n)+1),2):if n%i==0:return Falsereturn Truen=int(input())temp=0 for i in range(5,n+1,2):if is_prime(i) and is_prime(i-2):temp+=1 print(temp)

總結

以上是生活随笔為你收集整理的PAT (Basic Level) Practice （中文）1007 素数对猜想 （20 分)的全部內容，希望文章能夠幫你解決所遇到的問題。

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