PAT练习题：素数对猜想

让我们定义d_nd​n​​为：d_n = p_{n+1}-p_nd​n​​=p​n+1​​−p​n​​，其中p_ip​i​​是第$i$个素数。显然有d_1 = 1d​1​​=1，且对于$n>1$有d_nd​n​​是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N(<10^5<10​5​​)，请计算不超过N的满足猜想的素数对的个数。

输入格式:

输入在一行给出正整数N。

输出格式:

在一行中输出不超过N的满足猜想的素数对的个数。

输入样例:

20

输出样例:

4

解题思路：

1.先求出N以内所以素数 2.比较大小，并求素数对个数

代码示例：

#include<stdio.h> int main(){ int i,j,n,m=1,num=0; scanf("%d",&n); int isPrime[n]; for(i=1;i<=n;i++) //设置isPrime数组，是素数存1，不是为0 isPrime[i]=1; for(i=2;i<n;i++){ //找出N以内所以素数 if(isPrime[i]){ for(j=2;i*j<=n;j++){ isPrime[i*j]=0; } } } for(i=3;i<=n;i++){ //将找出的素数存放到isPrime数组中 if(isPrime[i]){ isPrime[m]=i; isPrime[m+1]=0; m++; } } for(i=1;isPrime[i]!=0;i++){ //比较大小，计算个数 if(isPrime[i]-isPrime[i-1]==2) num++; } printf("%d",num); }