题目

设 f[i] 表示两个质数的和为 i 的方案数，则 a n s = ∑ 1 n f [ i ] × f [ n − i ] ans =\sum_1^n f[i] × f[n − i] ans=∑1n​f[i]×f[n−i]。
注意到 n 以内的质数不超过 $O(\frac{n}{log n}) $个，而总和不超过 n 的质数只有大约 5 × 107 对，暴力枚举求出所有 f 即可。时间复杂度 O ( n 2 l o g 2 n ) O(\frac{n^2}{log^2n}) O(log2nn2​)——by Claris
此题要注意卡常

#include<bits/stdc++.h>
using namespace std;
const int N=150002;
typedef long long ll;
int n,k,pri[N/10],b[N],i,j,f[N];
ll ans;
int main(){
    scanf("%d",&n);
    for (i=2;i<=n;i++){
        if (!b[i]) pri[k++]=i;
        for (j=0;j<k && i*pri[j]<=n;j++){
            b[i*pri[j]]=1;
            if (i%pri[j]==0) break;
        }
    }
    for (i=0;i<k && (pri[i]<<1)<=n;i++){
    	f[pri[i]<<1]++;
    	for (j=i+1;j<k && pri[i]+pri[j]<=n;j++) f[pri[i]+pri[j]]+=2;
	}
	for (i=1;i<=n/2;i++) ans+=f[i]*f[n-i]*2;
	if (n%2==0) ans-=f[n/2]*f[n/2];
	printf("%lld",ans);
}