題目信息

讓我們定義 d_n 為：d_n = p_n+1 - p_n，其中 p_i 是第i個(gè)素?cái)?shù)。顯然有 d₁=1 且對(duì)于n&gt1有 d_n 是偶數(shù)?！八?cái)?shù)對(duì)猜想”認(rèn)為“存在無(wú)窮多對(duì)相鄰且差為2的素?cái)?shù)”。
現(xiàn)給定任意正整數(shù)N (< 10⁵)，請(qǐng)計(jì)算不超過(guò)N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。
輸入格式：每個(gè)測(cè)試輸入包含1個(gè)測(cè)試用例，給出正整數(shù)N。
輸出格式：每個(gè)測(cè)試用例的輸出占一行，不超過(guò)N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。
輸入樣例：
20
輸出樣例：
4

分析

主要先寫個(gè)判斷素?cái)?shù)的函數(shù)。有兩種方法：
（1）判斷n是否被2~n-1整除
（2）判斷n是否被2~根號(hào)n整除
第一種方法提交上去，有的測(cè)試點(diǎn)會(huì)運(yùn)行超時(shí)，故用第二種方法。

代碼

#include<stdio.h>
bool isPrime(int n){
  for(int i=2;i*i<=n;i++){
    if(n%i==0) return false; 
  }           
  return true;
}
int main(){
    int n;int cp=0;
    scanf("%d",&n);
    for(int i=5;i<=n;i++){
      if(isPrime(i)&&isPrime(i-2)) cp++; 
    }
    printf("%d",cp);
    return 0;
} 

測(cè)試結(jié)果

image.png