PAT B1007 素数对猜想(C++)

PAT甲级目录 | PAT乙级目录

题目描述

让我们定义 $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

易错点:

  • 1 不是素数,2是最小的素数

也许陌生的知识点

1
2
3
4
5
6
bool isprime(int x){
for(int i = 2; i * i <= x; i++){
if(x % i == 0) return false;
}
return true;
}
  • 判断素数最好用的模板,记住就好

代码示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
bool isprime(int x){
for(int i = 2; i * i <= x; i++){
if(x % i == 0) return false;
}
return true;
}
int main(){
int N, cnt = 0;
cin >> N;
for(int i = 2; i <= N - 2; i++){
if(isprime(i) && isprime(i + 2)){
cnt++;
}
}
cout << cnt;
return 0;
}