【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;}