Skip to content

1007 素数对猜想

Statement

Metadata

  • 作者: CHEN, Yue
  • 单位: 浙江大学
  • 代码长度限制: 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

Solution

#include <bits/stdc++.h>
using namespace std;
#define MAXN 100000
int isPrime[MAXN];
void getprime(int x) {
    int i, j, k, n;
    isPrime[1] = 0;
    for (i = 2; i <= x; i++) {
        k = sqrt(i);
        for (j = 2; j <= k; j++) {
            if (0 == i % j)
                break;
        }
        if (j > k)
            isPrime[i] = 1;
        else
            isPrime[i] = 0;
    }
}
int main() {
    int n, i, total = 0;
    cin >> n;
    getprime(n);
    if (n >= 5)
        for (i = 5; i <= n; i++) {
            if (isPrime[i] && isPrime[i - 2] && !isPrime[i - 1])
                total++;
        }
    cout << total << endl;
}
Last update: May 4, 2022
Back to top