This problem asks us to find two primes, $A$ and $B$, that satisfy $N={\displaystyle \frac{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 $2000000$ 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=538711$ 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.