Ah... more prime numbers. In this problem we are asked to verify Goldbach's Conjecture for even numbers, n with 6 <= n <= 1,000,000. Similar to UVa 10140 - Prime Distance, the number of test cases to process is not given in the input. Not always, but often, this style of input is an indicator that some kind of preprocessing step is required to avoid TLE (Time limit exceeded). And also like UVa 10140, that preprocessing step involves computing some primes once and reusing the results for one or more cases to save time.
To accomplish the aforementioned precomputation, we will be using the Sieve of Eratosthenes in tandem with a primality test optimization for large primes. If you have not seen an implementation for Sieve before, an implementation is provided below, and make sure you understand what's going on before continuing.
Once our precomputation is complete, all we need to do for each case is loop over the interval [0, n-1] and test primality for the outermost elements. By outermost, I mean integers i and n - i, whose sum will always give us n for all 0 <= i < n. The output requires we print one line of the form n = a + b, where a and b are odd primes, and if there is more than one pair of odd primes whose sum is n, we must choose a and b such that b - a is maximized.
Since we know n = a + b, and n = i + (n - i), it follows that a = i, and b = n - i, for all i, 0 <= i < n The difference (n - i) - i shrinks as i moves from 0 to n - 1, so we know the first solution found, if one exists, is the desired one. Lastly, we need to print Goldbach's conjecture is wrong, if no solution exists.