PAT-B-1007

1007 素数对猜想

题目

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

思路分析

暴力检索显然是 $O(n^2)$，但是只要黎曼猜想还叫黎曼猜想，素数分布情况就还是没被完全发掘的

先暴力一下，以后继续寻找其他方法

代码一 (5/6)

#include <iostream>

using namespace std;

bool isPrime(int num) {
    if (num % 2 == 0) {
        return false;
    }
    for (int i = 3; i < num; i+=2) {
        if (num % i == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    int count = 0;
    cin >> n;
    for (int i = 2; i <= n - 2; i++) {
        if (isPrime(i) && isPrime(i + 2)) {
            count++;
        }

    }
    cout << count;
    return 0;
}