题目

原题链接

让我们定义 d~n~ 为：d~n~ = p~n+1~ - p~n~，其中 p~i~ 是第i个素数。显然有 d~1~=1 且对于n>1有 d~n~ 是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。

现给定任意正整数N (< 10^5)，请计算不超过N的满足猜想的素数对的个数。

输入格式：每个测试输入包含1个测试用例，给出正整数N。

输出格式：每个测试用例的输出占一行，不超过N的满足猜想的素数对的个数。

输入样例：
20

输出样例：
4

解析

首先用线性筛法打出来质数表，然后判断质数表相邻的两个是否差为2即可
需要注意的是，遍历质数表有两个条件：

• 在质数表的可判断范围内
• 不超过输入的n

代码

C++解法

#include <cstring>
#include <iostream>
using namespace std;

const int maxn = 1e5 + 5;

int prime[maxn];
bool isPrime[maxn];
int pos;

void listPrime(int maxNum) {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    pos = 0;
    for (int i = 2; i <= maxNum; ++i) {
        if (isPrime[i])
            prime[pos++] = i;
        for (int j = 0; j < pos && i * prime[j] <= maxNum; ++j) {
            isPrime[i * prime[j]] = false;
            if (!(i % prime[j]))
                break;
        }
    }
}

int ans[maxn];
int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int n;
    cin >> n;
    listPrime(n);

    int cnt = 0;
    for (int i = 1; prime[i] <= n && i < pos; ++i) {
        if (prime[i] - prime[i - 1] == 2)
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

Python解法

def listPrime(MAX):
    isPrime = [True for i in range(MAX + 1)]
    isPrime[0] = isPrime[1] = False
    prime = []
    for i in range(2, MAX + 1):
        if isPrime[i]:
            prime.append(i)
        for j in range(0, len(prime)):
            if i * prime[j] > MAX:
                break
            isPrime[i * prime[j]] = False
            if not (i % prime[j]):
                break
    return prime


n = int(input())
prime = listPrime(n)

cnt = 0
i = 1
while 1:
    if i >= len(prime) or prime[i] > n:
        break
    if prime[i] - prime[i - 1] == 2:
        cnt += 1
    i += 1
print(cnt)

Java解法

import java.lang.reflect.Array;
import java.util.*;

class Main {

    public static final int maxn = 100005;
    public static int[] prime = new int[maxn];
    public static boolean[] isPrime = new boolean[maxn];
    public static int pos;

    public static void listPrime(int maxNum) {
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        pos = 0;

        for (int i = 2; i <= maxNum; ++i) {
            if (isPrime[i])
                prime[pos++] = i;
            for (int j = 0; j < pos && i * prime[j] <= maxNum; ++j) {
                isPrime[i * prime[j]] = false;
                if (i % prime[j] == 0)
                    break;
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        listPrime(n);
        int cnt = 0;
        for (int i = 1; i < pos && prime[i] <= n; ++i) {
            if (prime[i] - prime[i - 1] == 2)
                cnt++;
        }
        System.out.println(cnt);
        in.close();
    }

}