CCC '19 S2 - Pretty Average Primes

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 1.0s
Memory limit: 1G

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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^{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 1

4
8
4
7
21

Sample Output 1

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


  • -9
    349081547  commented on Feb. 14, 2020, 5:54 p.m. edit 2

    This comment is hidden due to too much negative feedback. Click here to view it.


  • -2
    biponroy  commented on Feb. 14, 2020, 3:58 a.m.

    Any tips to pass the second batch of test cases? Appears to be a case I missed in my code where I run into index out of bounds for the first test case of the second batch. The first batch was successful. (Written in Java).


  • -3
    nadinepi  commented on Feb. 7, 2020, 11:54 a.m.

    This was my output (for case 1), and it is saying it is wrong...

    3 13

    3 5

    3 11

    3 39

    I am not sure how this is wrong...How can I view what was inputted?


    • 20
      p1geon  commented on Feb. 7, 2020, 5:29 p.m.

      39 is not a prime


    • 0
      sushi  commented on Feb. 7, 2020, 12:06 p.m.

      Your output is most likely clipped so you will not be able to see the full output. Meaning that the output that was clipped might be correct, but the rest of your output may contain errors. For CCC problems, you can find the test-data on the official CCC website.


  • -4
    AryanG  commented on Aug. 10, 2019, 9:39 p.m.

    Nvm. I forgot to divide sizeof by int


  • -3
    AryanG  commented on Aug. 10, 2019, 9:38 p.m.

    Is there a reason I am getting RTE "floating point error" in c although I never do any weird arithmetic and never divide or mod by 0?


  • -6
    izeusify  commented on April 4, 2019, 10:13 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


  • -2
    GTATutors  commented on Feb. 26, 2019, 11:43 p.m.

    So CCC limit its time for solving problem to 1sec already? I thought previously, for all unspecifed questions, they limit it to 5 sec?


    • 5
      TimothyW553  commented on Feb. 26, 2019, 11:53 p.m.

      During the CCC, the problem was specifically limited to 1 second.


      • 1
        GTATutors  commented on Feb. 27, 2019, 5:00 p.m.

        I see! Thank you for your reply!


  • 2
    ai23  commented on Feb. 26, 2019, 5:22 p.m.

    My solution passed on the CCC but not here?


    • 1
      Rimuru  commented on Feb. 26, 2019, 5:50 p.m.

      Python is slow. Try submitting in PyPy.


      • 6
        ai23  commented on Feb. 26, 2019, 6:42 p.m.

        PyPy MLE's