00-自測(cè)2. 素?cái)?shù)對(duì)猜想 (20)

時(shí)間限制 400 ms 內(nèi)存限制 65536 kB 代碼長(zhǎng)度限制 8000 B 判題程序 Standard 作者 CHEN, Yue

讓我們定義 d_n?為：d_n?= p_n+1?- p_n，其中 p_i?是第i個(gè)素?cái)?shù)。顯然有 d₁=1 且對(duì)于n>1有 d_n?是偶數(shù)。“素?cái)?shù)對(duì)猜想”認(rèn)為“存在無窮多對(duì)相鄰且差為2的素?cái)?shù)”。

現(xiàn)給定任意正整數(shù)N (< 10⁵)，請(qǐng)計(jì)算不超過N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。

輸入格式：每個(gè)測(cè)試輸入包含1個(gè)測(cè)試用例，給出正整數(shù)N。

輸出格式：每個(gè)測(cè)試用例的輸出占一行，不超過N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。

輸入樣例： 20 輸出樣例： 4

---

提交代碼

?

1 #include <cstdio> 2 #include <cstring> 3 #include <string> 4 #include <queue> 5 #include <cmath> 6 #include <iostream> 7 using namespace std; 8 bool isprime[100005]; 9 int prime[10000],primenum=0; 10 void getprime(int n){ 11 memset(isprime,true,sizeof(isprime)); 12 isprime[0]=isprime[1]=false; 13 //cout<<primenum<<endl; 14 int i,j; 15 for(i=2;i<=n;i++){ 16 //cout<<i<<endl; 17 if(isprime[i]){ 18 //cout<<i<<endl; 19 for(j=i+i;j<=n;j+=i){ 20 //cout<<i<<" "<<j<<endl; 21 isprime[j]=false; 22 } 23 } 24 } 25 //cout<<primenum<<endl; 26 for(i=2;i<=n;i++){ 27 if(isprime[i]){ 28 prime[primenum++]=i; 29 //cout<<prime[primenum-1]<<endl; 30 } 31 } 32 //cout<<primenum<<endl; 33 } 34 int main(){ 35 int n,num=0,i; 36 getprime(100005); 37 scanf("%d",&n); 38 for(i=0;i<primenum-1&&prime[i+1]<=n;i++){ 39 if(prime[i+1]-prime[i]==2){ 40 //cout<<prime[i]<<endl; 41 num++; 42 } 43 } 44 cout<<num<<endl; 45 return 0; 46 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/Deribs4/p/4716711.html

總結(jié)

以上是生活随笔為你收集整理的pat00-自测2. 素数对猜想 (20)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。