1007 素?cái)?shù)對(duì)猜想 （20 分）
題目：讓我們定義d?n??為：d?n??=p?n+1???p?n??，其中p?i??是第i個(gè)素?cái)?shù)。顯然有d?1??=1，且對(duì)于n>1有d?n??是偶數(shù)?！八?cái)?shù)對(duì)猜想”認(rèn)為“存在無窮多對(duì)相鄰且差為2的素?cái)?shù)”。
現(xiàn)給定任意正整數(shù)N(<10?5??)，請(qǐng)計(jì)算不超過N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。
輸入格式:
輸入在一行給出正整數(shù)N。
輸出格式:
在一行中輸出不超過N的滿足猜想的素?cái)?shù)對(duì)的個(gè)數(shù)。
輸入樣例:
20
輸出樣例:
4
思路：判斷素?cái)?shù)，下面給出判斷素?cái)?shù)的兩種方法：
1）因此判斷一個(gè)整數(shù)m是否是素?cái)?shù)，只需把 m 被 2 ~ m-1 之間的每一個(gè)整數(shù)去除，如果都不能被整除，那么 m 就是一個(gè)素?cái)?shù)。
2)：另外判斷方法還可以簡化。m 不必被 2 ~ m-1 之間的每一個(gè)整數(shù)去除，只需被 2 ~根號(hào)m之間的每一個(gè)整數(shù)去除就可以了。如果 m 不能被 2 ~根號(hào)m間任一整數(shù)整除，m 必定是素?cái)?shù)。例如判別 17 是是否為素?cái)?shù)，只需使 17 被 2~4 之間的每一個(gè)整數(shù)去除，由于都不能整除，可以判定 17 是素?cái)?shù)。
原因：因?yàn)槿绻?m 能被 2 ~ m-1 之間任一整數(shù)整除，其二個(gè)因子必定有一個(gè)小于或等于根號(hào)m，另一個(gè)大于或等于根號(hào)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)素?cái)?shù)優(yōu)化算法：素?cái)?shù)篩法：
? ? 1.開一個(gè)大的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)的素?cái)?shù)了。
? ? 原理很簡單，就是當(dāng)i是質(zhì)(素)數(shù)的時(shí)候，i的所有的倍數(shù)必然是合數(shù)。如果i已經(jīng)被判斷不是質(zhì)數(shù)了，那么再找到i后面的質(zhì)數(shù)來把這個(gè)質(zhì)
數(shù)的倍數(shù)篩掉。
? ? 一個(gè)簡單的篩素?cái)?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個(gè)單元被標(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
? ? 這就是最簡單的素?cái)?shù)篩選法，對(duì)于前面提到的10000000內(nèi)的素?cái)?shù)，用這個(gè)篩選法可以大大的降低時(shí)間復(fù)雜度。(同時(shí)博客上還提出了bool的優(yōu)化：即是只篩奇數(shù)（從3開始，因?yàn)?是素?cái)?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);
//遍歷素?cái)?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é)果：還存在錯(cuò)誤（一刷是這樣的結(jié)果，還不知道哪里錯(cuò)了，等待二刷再改）
總結(jié)：這道題我寫了差不多六個(gè)小時(shí)，暴露了我的代碼能力的薄弱，希望這幾個(gè)月能真正靜下心來刷題。
