PAT乙级1007 || 素数对猜想（详解，C/C++示例，测试点分析）

Posted on In

素数对猜想

题目描述

让我们定义$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的满足猜想的素数对的个数。

输入样例

1
20

输出样例

1
4

问题解决

解题思想

此题的关键点为：

  • 判断一个数i是否为素数
  • 记录下刚刚判断的最近邻的素数

判定i是否为素数这里我们用判断 $i$ 能够被$2 - \sqrt{i}$中的某个数所整除，如果$2 - \sqrt{i}$中存在一个数能整除 $i$，则i就不是素数；反之，如果$2 - \sqrt{i}$中没有能整除 $i​$ 的数，则i就是素数。

代码示例（C）

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
#include <stdio.h>
#include <math.h>
int main()
{
    int n,i,j,pre_prime,count = 0,flag;
    scanf("%d",&n);
    pre_prime = 2;//初始化上一个素数为2
    for(i = 3; i <= n; i++){//当前素数的判定从3开始
        flag = 0;
        for(j = 2; j <= sqrt(i); j++){
            if(i % j == 0){
                flag = 1;
                break;
            }
        }
        if(flag == 0){
            //如果i是素数（即flag == 0）
            //且当前素数与上一个素数差为2
            if(i-pre_prime == 2){
                count++;
            }
            pre_prime = i;//更新上一个素数为当前素数
        }
    }
    printf("%d\n",count);
    return 0;
}

题目来源：PAT乙级1007
作者：CHEN, Yue
单位：浙江大学

稀罕作者