https://acm.hdu.edu.cn/showproblem.php?pid=2098
时间复杂度
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=2e4+520; bool st[N]; ll prime[N],cnt; void get_prime(ll n) { for(int i=2;i<=n;i++) { if(!st[i]) prime[cnt++]=i; for(int j=0;prime[j]<=n/i;j++) { st[prime[j]*i]=1; if(i%prime[j]==0) break; } } } int main() { get_prime(N); ll n,res; while(scanf("%lld",&n),n) { res=0; for(ll i=n/2;i>=2;i--) { if(!st[i]&&!st[n-i]&&(i!=(n-i))) res++;//素数有两千个,一次就要四次方,平方就要1e8,多来几个直接超时,但是一个知道了,那么另外一个就不用遍历了,直接判断即可 } cout<<res<<‘\n‘; } return 0; }