题解 | 素数对

#include <cstring>
#include <iostream>
#include <vector>
#define N 1000001
using namespace std;

bool p[N];

int main() {
    memset(p, true, sizeof(p));
    p[0] = p[1] = false;
    int n, x, ans=0;
    for (int i = 2; i <= 1000; i++) { //埃拉托斯特尼筛素数法
        if (p[i]) {
            x = i * i;
            while (x <= N) {
                p[x] = false;
                x += i;
            }
        }
    }

    cin>>n;
    if(n>=2) ans++;
    for(int i=3;i*i<=n+2;i+=2){
        if(!p[i]) continue;
        if(p[i*i-2]) ans+=2;          
    }
    cout<<ans;
    return 0;
}