UVa 543 Goldbach‘s Conjecture

题目描述

题目要求验证哥德巴赫猜想：每个大于等于444的偶数可以表示为两个奇素数之和。对于给定的偶数nnn（6≤n<10000006 \le n < 10000006≤n<1000000），输出n=a+bn = a + bn=a+b，其中aaa和bbb为奇素数，且b−ab - ab−a最大（即aaa尽可能小）。若不存在这样的素数对，输出Goldbach's conjecture is wrong.

输入格式

输入包含多个测试用例，每行一个偶数nnn，输入以n=0n = 0n=0结束。

输出格式

对于每个测试用例，输出一行，格式如n = a + b。

样例

输入

8 20 42 0

输出

8 = 3 + 5 20 = 3 + 17 42 = 5 + 37

题目分析

本题的核心是素数判断和查找。

素数预处理

由于n<1000000n < 1000000n<1000000，可以使用埃拉托色尼筛法（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)，可接受。

代码实现

// Goldbach's Conjecture// UVa ID: 543// Verdict: Accepted// Submission Date: 2016-08-07// UVa Run Time: 0.010s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intprimes[1000001]={0};for(inti=3;i<=1000000;i+=2)if(primes[i]==0)for(intj=2*i;j<=1000000;j+=i)primes[j]=-1;intn;while(cin>>n,n){for(inti=3;i<=500000;i+=2)if(primes[i]==0&&primes[n-i]==0){cout<<n<<" = "<<i<<" + "<<(n-i)<<'\n';break;}}return0;}