## CCC '19 S2 - Pretty Average Primes

View as PDF

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

Problem type

For various given positive integers , find two primes, and such that is the average (mean) of and . That is, should be equal to .

Recall that a prime number is an integer which is only divisible by and . For example, , , , , are the first few primes, and , , , are not prime numbers.

#### Input Specification

The first line of input is the number , which is the number of test cases. Each of the next lines contain one integer .

For 6 of the available 15 marks, all .

#### Output Specification

The output will consist of lines. The line of output will contain two integers, and , separated by one space. It should be the case that and that and are prime numbers.

If there are more than one possible and for a particular , output any such pair. The order of the pair and does not matter.

It will be the case that there will always be at least one set of values and for any given .

#### 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:

It is interesting to note, that we can also write

and so any of these pairs could have also been used in output. There is no pairs of primes other than and which average to the value of .

##### 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 , and your task is to find two primes and such that .

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

am i allowed to precompute prime numbers or not? because if not i dont see how this is possible with the time constraints.

• 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?

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

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

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