AcWing 1292. 哥德巴赫猜想
原题链接
简单
作者:
吴鑫
,
2021-02-09 13:35:05
,
所有人可见
,
阅读 310
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int prime[N],cut;
bool st[N];
int n;
void primes(){
for(int i=2;i<=1000000;i++){
if(!st[i]) prime[cut++]=i;
for(int j=0;prime[j]<=1000000/i;j++){
st[prime[j]*i]=true;
if(i%prime[j]==0) break;
}
}
}
void solve(int a){
for(int i=1;prime[i]<=a/2;i++){
if(!st[a-prime[i]]) {
printf("%d = %d + %d\n",a,prime[i],a-prime[i]);
return ;
}
}
puts("Goldbach's conjecture is wrong.");
return ;
}
int main(){
primes();
while(cin>>n,n){
solve(n);
}
return 0;
}