PAT 乙級 1007 素數對猜想

NO IMAGE

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

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

輸入格式:

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

輸出格式:

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

輸入樣例:

20
輸出樣例:

4
作者: CHEN, Yue
單位: 浙江大學
時間限制: 200ms
記憶體限制: 64MB
程式碼長度限制: 16KB
首先這個題並不是很難。但是如果一開始就去暴力解題雖然不知道能不能過(我並沒有試過暴力),但無疑會浪費時間。如果我們將所有的素數提前篩選出來,然後做上標記之後在去找是否存在素數對是否會跟節省時間。當然測試樣例資料非常小的時候可能暴力是非常簡單的一種方法,本題要求資料為100000這樣的資料並不適合暴力去解。廢話不多說我們上程式碼。

#include<iostream>
using namespace std;
int main()
{
int ans[100010]={0};
for(int i=2;i<100010;i  )
{
if(ans[i]==0)
{
for(int j=i i;j<100010;j=j i)
ans[j]=1;
}
}                                      \\在此處先將陣列進行預處理使以素數為下標的陣列值為零
int x,count=0;                         \\x為題目要求輸入  count為計數器統計素數對的個數
cin>>x;
for(int i=2;i<x;i  )
{
if(ans[i]==0&&ans[i 2]==0&&i<x-2)  \\只要ans[i]與ans[i 2]的值同時為零 即為滿足條件的素數對 count  
count  ;
}
cout<<count;                            \\輸出題目要求結果
return 0;
}

這道題並沒有什麼需要特別值得注意的事項。
我作為一名新人寫的不好還請大家多多擔待。如果覺得寫的有什麼不足之處,歡迎在評論區指出。