题解 | 素数对

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+10;

int n;

map<int,bool> mp;
vector<int> v;
bool f[N];

int main(){
	
	for(int i=2;i<N;i++){
		if(!f[i]){
			mp[i]=true;
			v.push_back(i);
			for(int j=i*2;j<N;j+=i){
				f[j]=true;
			}
		}
	}
	cin>>n;
	int cnt=0;
	bool f_two=false;
	for(int i=0;i<v.size()&&v[i]<=n;i++){
		if(v[i]*v[i]-2>n) break;
		if(mp[v[i]*v[i]-2]==true){
//			cout<<v[i]<<endl;
			if(v[i]==2&&!f_two){
				cnt++;
				f_two=true;
			}
			else cnt+=2;
		}
	}
	
	cout<<cnt<<endl;

    return 0;
}