PAT Basic 1007 素数对猜想 (20) [数学问题-素数]

题目

让我们定义 dn 为：dn = pn+1 – pn，其中 pi 是第i个素数。显然有 d1=1 且对于n>1有 dn 是偶数。“素数对猜想”认为“存在⽆穷多对相邻且差为2的素数”。现给定任意正整数N (< 105)，请计算不超过N的满⾜猜想的素数对的个数。

输⼊格式：

每个测试输⼊包含1个测试⽤例，给出正整数N。

输出格式：

每个测试⽤例的输出占⼀⾏，不超过N的满⾜猜想的素数对的个数。

输⼊样例：

20

输出样例：

4

题目分析

给出整数N，判断不超过N的质数中，连续两个质数差为2的对数

解题思路

1. pre指针指向上一个质数
2. 判断当前数字是否为质数，若为质数
   
   2.1 更新pre=i；
   
   2.3 判断质数i与pre相差是否为2，若为2，计数器加1;

Code

Code 01

#include <iostream>

#include <cmath>

using namespace std;

bool isPrime(int n) {

	if(n<=1)return false;

	int sqr = (int)sqrt(1.0*n);

	for(int i=2; i<=sqr; i++) {

		if(n%i==0)return false;

	}

	return true;

}

int main(int argc, char * argv[]) {

	int n;

	scanf("%d",&n);

	int pre=3,cnt=0;

	for(int i=5; i<=n; i++) {

		if(isPrime(i)) {

			if(i-pre==2)cnt++;

			pre=i;

		}

	}

	printf("%d",cnt);

	return 0;

}