B1007 素数对猜想 (20 分)

B1007 素数对猜想 (20 分)

代码长度限制 16 KB

时间限制 200 ms

内存限制 64 MB

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

代码：

#include <iostream>
#include <cmath>

using namespace std;
const int maxN = 10010;
int prime[maxN];
int p_num = 0;

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

void gen_prime(int tn){
    for (int i = 2; i <= tn; ++i) {
        if (is_prime(i)) {
            prime[p_num] = i;
            p_num++;
        }
    }
}

int main() {
    int n, cnt = 0;
    scanf("%d", &n);
    gen_prime(n);
    for (int i = 1; i < p_num; ++i) {
        if (prime[i] - prime[i - 1] == 2)
            cnt++;
    }
    printf("%d", cnt);
    return 0;
}