[TOC] ### 題目描述 1007 素數對猜想。 題目：讓我們定義 dn 為：dn = pn+1 - pn，其中 pi 是第i個素數。顯然有 d1=1 且對于n>1有 dn 是偶數。“素數對猜想”認為“存在無窮多對相鄰且差為2的素數”。 現給定任意正整數N (< 105)，請計算不超過N的滿足猜想的素數對的個數。 輸入格式：每個測試輸入包含1個測試用例，給出正整數N。 輸出格式：每個測試用例的輸出占一行，不超過N的滿足猜想的素數對的個數。 輸入樣例： 20 輸出樣例： 4 ### 分析（偽代碼和知識點） 1.該題的意思是求出n之前的素數對的個數（n是輸入的數且素數對的差為2）根據題意可知該題需要一個判斷素數的函數，然后由主函數進行素數對個數的計算。所以大體框架如下： 　　　　int isprime(){ 　　　　　　//求素數函數 　　　　} 　　　　int main(){ 　　　　　　//輸入 　　　　　　//計算個數 　　　　　　//輸出 　　　　} 2.輸入： 　　　　int n; 　　　　scanf("%d"&n); 3.判斷是否為素數 　　　　int isprime(int n){ 　　　　　　//通過一個for循環判斷n是否為素數(遍歷n之前的數) 　　　　for(int i=0;i<n;i++){ 　　　　if(n%i==0){return 0}; 　　　　} 　　　　return 1;//如果返回1則為素數 　　　　} 4.計算個數(通過一個for循環計算) 　　　　int i,k; 　　　　for(i=3;i<=n-2;i++){ 　　　　if(isprime(i) && isprime(i+2)){ 　　　　　　　　k++; 　　　　　　 　　　　　　　//通過比較從i到n-2中有多少對差為2的素數，相應 　　　　　　　　　　的計數器加1 　　　　　　　} 　　　　} 5.輸出：輸出要求的個數,該個數是由通過一個計數器來實現的. 　　　　printf("%d",k); ### 代碼1 ``` #include <stdio.h> #include <math.h> int sushu(int x){ int t,j; t=(int)sqrt((double)x); for(j=2;j<=t;j++){ if(x%j==0){ return 0; } } if(j>t){ return 1; } } int main(void){ int i,n,k=0; scanf("%d",&n); for(i=3;i<=n-2;i++){ if(sushu(i)&&sushu(i+2)){ k++; } } printf("%d",k); } ``` ###代碼2 ~~~ #include <stdio.h> #include <math.h> int isPrime(int n) { int i; if (n == 1) return 0; else if (n == 2) return 1; else if (n % 2 == 0) return 0; else { for(i=3;i*i<=n;i++){ if( n % i==0) return 0; } return 1; } } int main(void) { int n; scanf("%d", &n); int pair_cnt = 0; int i; for (i = 2; i < n; i++) { if (isPrime(i) && isPrime(i + 2) && (i + 2) <= n){ // printf("%d,%d ",i,i+2); pair_cnt++; } } printf("%d\n", pair_cnt); return 0; } ~~~  ###代碼3 ~~~ #include <stdio.h> #include <math.h> int isPrime(int n) { if (n == 1) return 0; else if (n == 2 || n == 3) return 1; else if (n % 2 == 0) return 0; else { int i, end; end = (int)sqrt(n) + 1; for (i = 3; i < end; i += 2) { if (n % i == 0) return 0; } return 1; } } int main(void) { int n; scanf("%d", &n); int pair_cnt = 0; int i; for (i = 2; i < n; i++) { if (isPrime(i) && isPrime(i + 2) && (i + 2) <= n){ // printf("%d,%d ",i,i+2); pair_cnt++; } } printf("%d\n", pair_cnt); return 0; } ~~~