PAT乙级 素数对猜想（1007）c++实现
题目：
让我们定义dn为：dn=pn+1−pn，其中pi是第i个素数。显然有d1=1，且对于n>1有dn是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
**现给定任意正整数N(<105)，请计算不超过N的满足猜想的素数对的个数。
先理清大致做题思路，找素数，然后判定前后两个素数大小差值，如果是2就令sum++（sum代表差值为2的素数对个数）
理清好就开始构建具体算法，像这种输入范围1-10^5的题，一般都可以通过打表的方式以空间换时间避免运行超时。因此先通过第一次循环进行打表，是素数的话数组该位置变为1；然后进行第二次循环，这里我用temp1记录上一次b[i]==1的下标，通过判定i-temp1是否等于2来判断满足题目要求的素数对。
注意，在检查该数是否是素数时，循环终止条件最大值不要直接一个n上去，而是应取个绝对值就够了。我就是因为一开始设置为n，一直超时，代码如下：
#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;
int find(int n)
{
int j;
for(j=2;j<=sqrt(n);j++)
{
if(n%j==0)
return 0;
}
return 1;
}
int main()
{
int i,n,sum=0,temp1=-1,b[100001];
cin>>n;
for(i=0;i<100001;i++)
b[i]=0;
for(i=2;i<=n;i++)
{
if(find(i))//如果是素数
{
b[i]=1;
}
}
for(i=1;i<100001;i++)
{
if(b[i]==1)
{
if(temp1!=-1)//该下标位置取得的素数不是第一个素数，因为素数对要从第二个素数开始才能相减进行判断满不满足差值为2
{
if(i-temp1==2)
sum++;
}
temp1=i;
}
}
cout<<sum<<endl;
return 0;
}
运行结果如图：
欢迎评论区留言
觉得该篇文章有用的请不要忘记忘记点击右下角的大拇指~
欢迎大家关注我的公众号：Smooth前端成长记录
公众号同步更新CSDN博客内容，想方便阅读博客的C友可以来关注我的公众号以便获得更优良的阅读体验~