Woburn Challenge 1999

Goldfinger

Think back to the 1960s. Remember Goldfinger? Well, it appears he was cryofrozen and traveled back in time to the mid 1700s, where he was reanimated as his alter ego Goldbach, the famous mathematician. Coincidentally, MI6 cryofroze James Bond and sent him back to a similar time to thwart the latest evil plan of the evil genius. Goldbach plans to distract all of the world's greatest intelligentsia by having them work with the dreaded ... unproven conjecture. He knows that an unproven conjecture (especially one as fiendish as his Binary Goldbach Conjecture) is sheer craziness and will drive all of the world's mathematicians to insanity, thus resulting in an effective end to mathematical development, thus plunging the world into the Dark Ages once more. But where mathematicians fail, scientists (and doctors) reign supreme and James Bond will attempt to prove the theorem by a tried-and-true scientific method: proof by example.

Goldbach's Binary Conjecture: Every even number 4 ≤ n ≤ 16000 may be written as a sum of 2 primes. (Note that Goldbach believed that 1 was prime).

Input

A series of integers in the range 4 ≤ n ≤ 16000, terminated by the number -1.

Output

Output ALL distinct pairs of primes a,b (a ≤ b) such than n = a + b; leave a blank line after each output set. The output should come sorted, in increasing order, by the first number (a). There may be as many as 200 numbers in the input file. An input of '-1' denotes the end of data. (Recall that a prime number is one that has no divisors other than one and itself. Also, count "1" as a prime.)

Sample Input

4
8
-1

Sample Output

1 3
2 2

1 7
3 5

All Submissions
Best Solutions


Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Sep 29, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

???

I just went through and determined all prime numbers by the brute-force method.

Come on Bosco, if I, of all people, could figure it out, then you should be able to.

I'm getting time limit exceeded even with the sieve. I just created the array and found all prime numbers and then I stored all primes in another array and outputed them by just using an embedded for loop. Is it my outputing or my storing in another array that takes me so much time?

Your method of checking for pairs is simply too inefficient. If you know one of the numbers of the pair, you already know what the other should be - why would you need to use a loop to search for it?