首页 > 代码库 > IEEEXtreme 10.0 - Goldbach's Second Conjecture
IEEEXtreme 10.0 - Goldbach's Second Conjecture
这是 meelo 原创的 IEEEXtreme极限编程大赛题解
Xtreme 10.0 - Goldbach‘s Second Conjecture
题目来源 第10届IEEE极限编程大赛
https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/goldbachs-second-conjecture
An integer p > 1 is called a prime if its only divisors are 1 and p itself. A famous conjecture about primes is Goldbach‘s conjecture, which states that
Every even integer greater than 2 can be expressed as the sum of two primes.
The conjecture dates back to the year 1742, but still no one has been able to come up with a proof or find a counterexample to it. We considered asking you prove it here, but realized it would be too easy. Instead we present here a more difficult conjecture, known as Goldbach‘s second conjecture:
Every odd integer greater than 5 can be expressed as the sum of three primes.
In this problem we will provide you with an odd integer N greater than 5, and ask you to either find three primes p1, p2, p3 such that p1 + p2 + p3 = N, or inform us that N is a counterexample to Goldbach‘s second conjecture.
Input Format
The input contains a single odd integer 5 < N ≤ 1018.
Output Format
Output three primes, separated by a single space on a single line, whose sum is N. If there are multiple possible answers, output any one of them. If there are no possible answers, output a single line containing the text "counterexample" (without quotes).
Sample Input
65Sample Output
23 31 11Explanation
In the sample input N is 65. Consider the three integers 11, 23, 31. They are all prime, and their sum is 65. Hence they form a valid answer. That is, a line containing "11 23 31", "23 31 11", or any permutation of the three integers will be accepted. Other possible answers include "11 37 17" and "11 11 43".
题目解析
将一个奇数分解为三个质数，奇数最大有1018。可以遍历前两个质数，然后判断奇数与两个质数的差是否仍未质数。如果3个质数都有1017，那么肯定会超时。
事实上是，存在解前两个质数都不超过1000。这个时候关键的问题成为了，如何判断一个规模有1018的数为质数。常规的方法复杂度为O(sqrt(n))，会超时。这时候需要一点数论的知识，Miller–Rabin质数测试能够在O((logn)2)判断一个数是否为质数。算法在维基百科详细的介绍。下面程序里的Miller–Rabin质数测试使用的是github上的代码。
程序
C++
#include <cmath>#include <cstdio>#include <vector>#include <iostream>#include <algorithm>#include <bitset>using namespace std;#define MAXN 1000typedef unsigned long long ULL;typedef long long LL;bitset<MAXN> nums;int primes[MAXN];int num_prime = 0;void getPrimes(long long max) { // get all primes under max for(int i=2; i<=sqrt(max+0.5); i++) { if(nums[i] == false) { primes[num_prime] = i; num_prime++; for(long long n=2*i; n<max; n+=i) { nums[n] = true; } } } for(int i=int(sqrt(max+0.5))+1; i<max; i++) { if(nums[i] == false) { primes[num_prime] = i; num_prime++; } }}LL MultiplyMod(LL a, LL b, LL mod) { //computes a * b % mod ULL r = 0; a %= mod, b %= mod; while (b) { if (b & 1) r = (r + a) % mod; b >>= 1, a = ((ULL) a << 1) % mod; } return r;}template<typename T>T PowerMod(T a, T n, T mod) { //computes a^n % mod T r = 1; while (n) { if (n & 1) r = MultiplyMod(r, a, mod); n >>= 1, a = MultiplyMod(a, a, mod); } return r;}template<typename T>bool isPrime(T n) { //determines if n is a prime number const int pn = 9, p[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23 }; for (int i = 0; i < pn; ++i) if (n % p[i] == 0) return n == p[i]; if (n < p[pn - 1]) return 0; T s = 0, t = n - 1; while (~t & 1) t >>= 1, ++s; for (int i = 0; i < pn; ++i) { T pt = PowerMod<T> (p[i], t, n); if (pt == 1) continue; bool ok = 0; for (int j = 0; j < s && !ok; ++j) { if (pt == n - 1) ok = 1; pt = MultiplyMod(pt, pt, n); } if (!ok) return 0; } return 1;}int main() { long long n; cin >> n; getPrimes(MAXN); for(int i=0; i<num_prime; i++) { for(int j=i; j<num_prime; j++) { if(isPrime(n-primes[j]-primes[i])) { printf("%lld %lld %lld", primes[i], primes[j], n-primes[i]-primes[j]); return 0; } } } return 0;}
博客中的文章均为 meelo 原创，请务必以链接形式注明 本文地址
IEEEXtreme 10.0 - Goldbach's Second Conjecture