1007 素数对猜想 （20 分）
题目：让我们定义d?n??为：d?n??=p?n+1???p?n??，其中p?i??是第i个素数。显然有d?1??=1，且对于n>1有d?n??是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<10?5??)，请计算不超过N的满足猜想的素数对的个数。
输入格式:
输入在一行给出正整数N。
输出格式:
在一行中输出不超过N的满足猜想的素数对的个数。
输入样例:
20
输出样例:
【PAT乙级（1007）】4
思路：判断素数，下面给出判断素数的两种方法：
1）因此判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。
2)：另外判断方法还可以简化。m 不必被 2 ~ m-1 之间的每一个整数去除，只需被 2 ~根号m之间的每一个整数去除就可以了。如果 m 不能被 2 ~根号m间任一整数整除，m 必定是素数。例如判别 17 是是否为素数，只需使 17 被 2~4 之间的每一个整数去除，由于都不能整除，可以判定 17 是素数。
原因：因为如果 m 能被 2 ~ m-1 之间任一整数整除，其二个因子必定有一个小于或等于根号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语言中文网）
3)素数优化算法：素数筛法：
1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为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数组中的值为true的单元的下标，就是所求的n以内的素数了。
原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质
数的倍数筛掉。
一个简单的筛素数的过程：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个单元被标成false,其余为true。
第 2 步开始：
i=3;
由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为false.
i=4;
由于prime[4]=false,不在继续筛法步骤。
i=5;
由于prime[5]=true, 把prime[10],[15],[20],[25],[30]标为false.
i=6>sqrt(30)算法结束。
第 3 步把prime[]值为true的下标输出来：
for(i=2;
i<=30;
i++)
if(prime[i]) printf("%d ",i);
结果是 2 3 5 7 11 13 17 19 23 29
这就是最简单的素数筛选法，对于前面提到的10000000内的素数，用这个筛选法可以大大的降低时间复杂度。(同时博客上还提出了bool的优化：即是只筛奇数（从3开始，因为2是素数），可以一试。
(作者：liukehua123来源：CSDN原文：https://blog.csdn.net/liukehua123/article/details/5482854)
代码：
#include
#include
int main()
{
int prime[100000];
int n,m,i,j,k=2,count=0;
prime[0]=2;
prime[1]=3;
scanf("%d",&n);
//遍历素数表
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;
}
结果：还存在错误（一刷是这样的结果，还不知道哪里错了，等待二刷再改）
文章图片
总结：这道题我写了差不多六个小时，暴露了我的代码能力的薄弱，希望这几个月能真正静下心来刷题。
