傳送門

https://pintia.cn/problem-sets/994805260223102976/problems/994805317546655744

題目

讓我們定義 dn為：dn = pn + 1- pn，其中 pi是第i個素數(shù)。顯然有 d1=1 且對于n>1有 dn是偶數(shù)?！八財?shù)對猜想”認為“存在無窮多對相鄰且差為2的素數(shù)”。
現(xiàn)給定任意正整數(shù)N (< 105)，請計算不超過N的滿足猜想的素數(shù)對的個數(shù)。
輸入格式：每個測試輸入包含1個測試用例，給出正整數(shù)N。
輸出格式：每個測試用例的輸出占一行，不超過N的滿足猜想的素數(shù)對的個數(shù)。
輸入樣例：
20
輸出樣例：
4

分析

C++和Java實現(xiàn)方法都是：
運用篩選法求素數(shù)，也就是建立一個素數(shù)表，簡單來說就是從2開始將2的倍數(shù)（不超過N）的下標對應的數(shù)組置為false，然后從3開始計算，直到超過N為止，然后遍歷數(shù)組，根據(jù)true or false，判斷素數(shù)的個數(shù)，最后輸出即可。
這里我用的只是最低級的篩法，如果你想學習更高級的篩法建議搜索下相關資料。

源代碼

//C/C++實現(xiàn)
#include <stdio.h>
#include <iostream>

using namespace std;

bool array[100000];

int main(){
    int n;
    scanf("%d", &n);
    for(int i=2;i<n/2+1;i++){
        for(int j=2;j*i<=n;j++){
            array[i*j] = true;
        }
    }
    int count = 0, tmp = 2;
    for(int k=2;k<=n;k++){
        if(array[k] == false){
            if(k - tmp == 2){
                count ++;
                tmp = k;
            }
            else{
                tmp = k;
            }
        }
    }
    printf("%d\n", count);
    return 0;
}

//Java實現(xiàn)
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String s = bufferedReader.readLine();
        int n = 0;
        try{
            n = Integer.valueOf(s);
        }catch(Exception e){
            System.exit(0);
        }
        if(n < 1 || n > 99999){
            System.exit(0);
        }
        int[] prime = new int[n+1];
        boolean[] isNotPrime = new boolean[n+1];
        for(int i=2;i<=n/2;i++){
            if(!isNotPrime[i]){
                for(int j=i*2;j<=n;j+=i){
                    isNotPrime[j] = true;
                }
            }
        }
        int size = 0;
        for(int k=2;k<=n;k++){
            if(!isNotPrime[k]){
                prime[size ++] = k;
            }
        }
        int count = 0;
        for(int i=0;i<prime.length-1;i++){
            if(prime[i+1]-prime[i] == 2){
                    count ++;
            }
        }
        System.out.println(count);
    }
}