题解 | 素数对

#include<iostream>
#include<algorithm>
#include<cstring>
#include<unordered_map>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MAXN 1000010
int primes[MAXN],cnt;
bool st[MAXN];
int a[MAXN];
unordered_map<int,int> mp;
unordered_map<int,int> np;
void gprimes(int n){
    for(int i=2;i<=n;i++){
        if(!st[i])primes[cnt++]=i;
        for(int j=0;primes[j]*i<=n;j++){
            st[i*primes[j]]=1;
            if(i%primes[j]==0)break;
        }
    }
}
void init(){
    for(int i=0;primes[i]<10000;i++)np[primes[i]*primes[i]]=1;
    for(int i=1;i<cnt;i++)
    if(np[2+primes[i]])mp[primes[i]]=2;
    for(int i=1;i<=500000;i++)a[i]=a[i-1]+mp[i];
//    for(int i=1;i<=100;i++)cout<<a[i]<<" ";
}
void solve(){
	int n;
    cin>>n;
    if(n==2){
        cout<<1<<endl;
        return ;
    }
    cout<<a[n]<<endl;
}
signed main(){
	ios;
	int t=1;
    gprimes(1000000);
    mp[4]=1;
    init();
	while(t--)
	solve();
	return 0;
}