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$ 的满足猜想的素数对的个数。

输入样例：

20

输出样例：

4

易错点：

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

也许陌生的知识点

bool isprime(int x){
  for(int i = 2; i * i <= x; i++){
    if(x % i == 0) return false;
  }
  return true;
}

• 判断素数最好用的模板，记住就好

代码示例：

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