> 文档中心 > 【PAT乙级】题解-1007 素数对猜想

【PAT乙级】题解-1007 素数对猜想

PAT :计算机程序设计能力考试:一个高校编程学习赛,内容基础,据说题目描述含糊不清,造成诸多理解错误。

第一观感是:输入输出样例极少,未给学生充分理解题目,提供更多辅助。

PAT 乙级:只涉及基础编程,最难到排序算法。适合基础语法学习阶段的同学。

问题描述

让我们定义 d n d_n dn 为: d n d_n dn = pn+1 p_{n+1} pn+1 - p n p_n pn,其中 p i p_i pi 是第 i 个素数。显然有 d 1 = 1 d_1 = 1 d1=1,且对于 n>1 有 d n d_n dn 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为 2 的素数”。现给定任意正整数 N (<105),请计算不超过 N 的满足猜想的素数对的个数。

输入格式

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

输出格式

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

输入输出样例

输入样例 输出样例
20 4
7 2

样例解释:无

题解 1

思路分析:遍历 3~n 中,所有的素数,判断当前素数和前一个素数的差,是否为 2,初始前一个素数定义为 2。

#includeusing namespace std;bool isPrime(int x);int main() {int n;cin >> n;int cnt = 0;int pre = 2;// 记录前一个素数for(int i = 3; i <= n; i++) {if(isPrime(i)) {if(i - pre == 2) {cnt ++;}pre = i;}}cout << cnt << endl;return 0;} bool isPrime(int x) {if(x < 2) return false;for(int i = 2; i * i <= x; i++) {if(x % i == 0) return false;}return true;}