Canadian Computing Competition: 2019 Stage 1, Senior #2
For various given positive integers 
~N > 3~, find two primes, 
~A~ and 
~B~ such that 
~N~ is the average (mean) of ~A~ and ~B~. That is, ~N~ should be equal to 
~\dfrac{A + B}{2}~.
Recall that a prime number is an integer 
~P > 1~ which is only divisible by 
~1~ and 
~P~. For example, 
~2~, 
~3~, 
~5~, 
~7~, 
~11~ are the first few primes, and 
~4~, 
~6~, 
~8~, 
~9~ are not prime numbers.
Input Specification
The first line of input is the number 
~T~ 
~(1 \le T \le 1\,000)~, which is the number of test cases. Each of the next ~T~ lines contain one integer 
~N_i~ 
~(4 \le N_i \le 1\,000\,000, 1 \le i \le T)~.
For 6 of the available 15 marks, all 
~N_i < 1\,000~.
Output Specification
The output will consist of ~T~ lines. The 
~i^\text{th}~ line of output will contain two integers, 
~A_i~ and 
~B_i~, separated by one space. It should be the case that 
~N_i=\dfrac{A_i + B_i}{2}~ and that ~A_i~ and ~B_i~ are prime numbers.
If there are more than one possible ~A_i~ and ~B_i~ for a particular ~N_i~, output any such pair. The order of the pair ~A_i~ and ~B_i~ does not matter.
It will be the case that there will always be at least one set of values ~A_i~ and ~B_i~ for any given ~N_i~.
Sample Input
4
8
4
7
21
Sample Output
3 13
5 3
7 7
13 29
Explanation of Possible Output for Sample Input
Notice that:
$$\displaystyle \begin{align}
8 &= \frac{3 + 13}{2}, \\
4 &= \frac{5 + 3}{2}, \\
7 &= \frac{7 + 7}{2}, \\
21 &= \frac{13 + 29}{2}.
\end{align}$$
It is interesting to note, that we can also write
$$\displaystyle \begin{align}
8 &= \frac{5 + 11}{2} \\
21 &= \frac{5 + 37}{2} = \frac{11 + 31}{2} = \frac{19 + 23}{2} \\
7 &= \frac{3 + 11}{2}
\end{align}$$
and so any of these pairs could have also been used in output. There is no pairs of primes other than ~3~ and ~5~ which average to the value of ~4~.
Footnote
You may have heard about Goldbach's conjecture, which states that every even integer greater than 2 can be expressed as the sum of two prime numbers. There is no known proof, yet, so if you want to be famous, prove that conjecture (after you finish the CCC).
This problem can be used to help verify that conjecture, since every even integer can be written as 
~2N~, and your task is to find two primes ~A~ and ~B~ such that 
~2N = A + B~.
Comments
How in the world does an algorithm that runs
pass a time limit of 1 second?
I rewrote the editorial to not have this problem.
Anyone know how I can make my code not TLE? I've tried submitting in both Python (https://dmoj.ca/submission/6984436) and PyPy (https://dmoj.ca/submission/6984444) and somehow PyPy was even slower than Python. I've already implemented caching and am not sure what to optimize.
Can N = A = B?
yes, please see the sample for
This comment is hidden due to too much negative feedback. Show it anyway.
Yes https://dmoj.ca/problem/ccc19s2/rank/?language=PY2&language=PY3&language=PYPY&language=PYPY3
This comment is hidden due to too much negative feedback. Show it anyway.
It is possible to pass by precomputing primes, and it is also possible to pass by not precomputing primes. Both methods pass within the time limit.
So CCC limit its time for solving problem to 1sec already? I thought previously, for all unspecifed questions, they limit it to 5 sec?
During the CCC, the problem was specifically limited to 1 second.
I see! Thank you for your reply!
My solution passed on the CCC but not here?
Python is slow. Try submitting in PyPy.
PyPy MLE's