This problem asks us to find two primes, ~A~ and ~B~, that satisfy ~N = \dfrac{A+B}{2}~. Equivalently, ~A+B = 2N~.

Approach 1

A straightforward approach is to test all possible values of ~A~ and ~B~. For example, we can use a for-loop that goes from ~A = 2~ to ~A = 2N~. Then we can calculate ~B~ using the equation ~B = 2N-A~. Once we have ~A~ and ~B~, we need to check if ~A~ and ~B~ are prime by using a primality test.

One approach is trial division. Suppose ~x~ is the input number. If the for-loop iterates from ~i = 2~ to ~i = x-1~, then trial division will take ~\mathcal{O}(x)~ time.

In practice, the overall time complexity is slightly slower than ~\mathcal{O}(TN)~. This is enough to get 6/15.

A slightly faster approach is to use trial division, ending at ~i = \lfloor \sqrt x \rfloor~ (or floor(sqrt(x))). Trial division will take ~\mathcal{O}(\sqrt x)~ time.

In practice, the overall time complexity is slightly slower than ~\mathcal{O}(T \sqrt N)~. This is enough to get 15/15.

Approach 2

Since ~A~ and ~B~ are at most ~2N~, we can precompute all the primes up to ~2\,000\,000~ using the sieve of Eratosthenes. This will take ~\mathcal{O}(N \log \log N)~ time. Then we can use Approach 1 with each primality test taking ~\mathcal{O}(1)~ time.

The worst possible test case is ~N = 538\,711~ which requires ~A = 601~. As a result, the overall time complexity is ~\mathcal{O}(N \log \log N + 601T)~. This is enough to get 15/15.

Note: These 2 approaches have an Eliden time complexity. For context, please see this comment. Please don't ask for a proof of the time complexity.