1007 素數(shù)對猜想 （20 分）
題目：讓我們定義d?n??為：d?n??=p?n+1???p?n??铜邮，其中p?i??是第i個素數(shù)蔚晨。顯然有d?1??=1握恳，且對于n>1有d?n??是偶數(shù)紊选。“素數(shù)對猜想”認為“存在無窮多對相鄰且差為2的素數(shù)”卸勺。
現(xiàn)給定任意正整數(shù)N(<10?5??)，請計算不超過N的滿足猜想的素數(shù)對的個數(shù)烫扼。
輸入格式:
輸入在一行給出正整數(shù)N曙求。
輸出格式:
在一行中輸出不超過N的滿足猜想的素數(shù)對的個數(shù)。
輸入樣例:
20
輸出樣例:
4
思路：判斷素數(shù)映企，下面給出判斷素數(shù)的兩種方法：
1）因此判斷一個整數(shù)m是否是素數(shù)悟狱，只需把 m 被 2 ~ m-1 之間的每一個整數(shù)去除，如果都不能被整除堰氓，那么 m 就是一個素數(shù)挤渐。
2)：另外判斷方法還可以簡化。m 不必被 2 ~ m-1 之間的每一個整數(shù)去除双絮，只需被 2 ~根號m之間的每一個整數(shù)去除就可以了浴麻。如果 m 不能被 2 ~根號m間任一整數(shù)整除得问，m 必定是素數(shù)。例如判別 17 是是否為素數(shù)软免，只需使 17 被 2~4 之間的每一個整數(shù)去除宫纬，由于都不能整除，可以判定 17 是素數(shù)膏萧。
原因：因為如果 m 能被 2 ~ m-1 之間任一整數(shù)整除漓骚，其二個因子必定有一個小于或等于根號m，另一個大于或等于根號m向抢。例如 16 能被 2认境、4、8 整除挟鸠，16=2*8叉信，2 小于 4，8 大于 4艘希，16=4*4硼身，4=√16，因此只需判定在 2~4 之間有無因子即可覆享。
舉例代碼地址：http://c.biancheng.net/view/498.html（C語言中文網(wǎng)）
3)素數(shù)優(yōu)化算法：素數(shù)篩法：
? ? 1.開一個大的bool型數(shù)組prime[]佳遂，大小就是n+1就可以了.先把所有的下標(biāo)為奇數(shù)的標(biāo)為true,下標(biāo)為偶數(shù)的標(biāo)為false.
? ? 2.然后：
? ? ? for( i=3; i<=sqrt(n); i+=2 )
? ? ? {? if(prime[i])
? ? ? ? ? for( j=i+i; j<=n; j+=i ) prime[j]=false;
? ? ? }
? ? 3.最后輸出bool數(shù)組中的值為true的單元的下標(biāo)，就是所求的n以內(nèi)的素數(shù)了撒顿。
? ? 原理很簡單丑罪，就是當(dāng)i是質(zhì)(素)數(shù)的時候，i的所有的倍數(shù)必然是合數(shù)凤壁。如果i已經(jīng)被判斷不是質(zhì)數(shù)了吩屹，那么再找到i后面的質(zhì)數(shù)來把這個質(zhì)
數(shù)的倍數(shù)篩掉。
? ? 一個簡單的篩素數(shù)的過程：n=30拧抖。
? ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
? ? 第 1 步過后2 4 ... 28 30這15個單元被標(biāo)成false,其余為true煤搜。
? ? 第 2 步開始：
? ? i=3;? 由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]標(biāo)為false.
? ? i=4;? 由于prime[4]=false,不在繼續(xù)篩法步驟。
? ? i=5;? 由于prime[5]=true, 把prime[10],[15],[20],[25],[30]標(biāo)為false.
? ? i=6>sqrt(30)算法結(jié)束唧席。
? ? 第 3 步把prime[]值為true的下標(biāo)輸出來：
? ? for(i=2; i<=30; i++)
? ? if(prime[i]) printf("%d ",i);
? ? 結(jié)果是 2 3 5 7 11 13 17 19 23 29
? ? 這就是最簡單的素數(shù)篩選法擦盾，對于前面提到的10000000內(nèi)的素數(shù)，用這個篩選法可以大大的降低時間復(fù)雜度淌哟。(同時博客上還提出了bool的優(yōu)化：即是只篩奇數(shù)（從3開始迹卢，因為2是素數(shù)），可以一試徒仓。
(作者：liukehua123來源：CSDN原文：https://blog.csdn.net/liukehua123/article/details/5482854)
代碼：
#include<stdio.h>
#include<math.h>
int main()
{
int prime[100000];
int n,m,i,j,k=2,count=0;
prime[0]=2;prime[1]=3;
scanf("%d",&n);
//遍歷素數(shù)表
m=sqrt(n);
for(i=2;i<=n;i++){
for(j=2;j<=m;j++){
if(i%j==0)break;}
if(j>m)prime[k++]=i;
}
//輸出
for(int d=0;d<=n;d++){
if(prime[d+1]-prime[d]==2)count++;
//printf("%d\n",prime[d]);
}
printf("%d",count);
return 0;
}
結(jié)果：還存在錯誤（一刷是這樣的結(jié)果婶希，還不知道哪里錯了，等待二刷再改）
總結(jié)：這道題我寫了差不多六個小時蓬衡，暴露了我的代碼能力的薄弱喻杈，希望這幾個月能真正靜下心來刷題彤枢。
