UVa 543 Goldbach‘s Conjecture

题目描述题目要求验证哥德巴赫猜想每个大于等于444的偶数可以表示为两个奇素数之和。对于给定的偶数nnn6≤n10000006 \le n 10000006≤n1000000输出nabn a bnab其中aaa和bbb为奇素数且b−ab - ab−a最大即aaa尽可能小。若不存在这样的素数对输出Goldbachs conjecture is wrong.输入格式输入包含多个测试用例每行一个偶数nnn输入以n0n 0n0结束。输出格式对于每个测试用例输出一行格式如n a b。样例输入8 20 42 0输出8 3 5 20 3 17 42 5 37题目分析本题的核心是素数判断和查找。素数预处理由于n1000000n 1000000n1000000可以使用埃拉托色尼筛法Sieve of Eratosthenes\texttt{Sieve of Eratosthenes}Sieve of Eratosthenes预先生成所有素数。注意111不是素数222是偶数素数但题目要求奇素数所以从333开始。查找策略对于给定的偶数nnn从333开始遍历奇数iii检查iii和n−in-in−i是否均为素数。由于n−in-in−i也是奇数且iii递增第一个找到的对即为aaa最小的对满足b−ab - ab−a最大。复杂度分析筛法O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn)每个查询O(n)O(n)O(n)可接受。代码实现// Goldbachs Conjecture// UVa ID: 543// Verdict: Accepted// Submission Date: 2016-08-07// UVa Run Time: 0.010s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intprimes[1000001]{0};for(inti3;i1000000;i2)if(primes[i]0)for(intj2*i;j1000000;ji)primes[j]-1;intn;while(cinn,n){for(inti3;i500000;i2)if(primes[i]0primes[n-i]0){coutn i (n-i)\n;break;}}return0;}