UVa 543

From Algorithmist

Contents 1 543 - Goldbach's Conjecture 2 Summary 3 Explanation 4 Input 5 Output

[edit] 543 - Goldbach's Conjecture

• http://acm.uva.es/p/v5/543.html

[edit] Summary

Goldbach's Conjecture is unproven, but is true for the input. (You will not have to print "Goldbach's conjecture is wrong.") Simply use the sieve, and use a naive algorithm, starting from going outwards, minimizing the distance between the two numbers.

[edit] Explanation

Goldbach's Conjecture have been confirmed up to very large numbers, and this is a trivial problem, given that you know how to implement the Prime Sieve of Eratosthenes.

[edit] Input

8
20
42
0

[edit] Output

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