Editorial for CCC '19 S2 - Pretty Average Primes
Submitting an official solution before solving the problem yourself is a bannable offence.
For this problem, we can use a simple for-loop to generate values of ~a~ and ~b~.
Set ~a = i~ and ~b = 2n - i~. Loop ~i~ through the integers from ~2~ to ~2n~.
Check if they are both prime and that ~2n~ is equal to ~a + b~.
Recall that an integer is prime if it is greater than 1 and cannot be formed by multiplying two smaller natural numbers.
For subtask 1, it is sufficient to loop ~i~ through the integers from ~2~ to ~n~ when checking if the integer is prime. If ~n~ is divisible by any of the values from ~2~ to ~n~, the integer is not prime.
This gives us an ~\mathcal O (TN^2)~ algorithm.
For subtask 2, an optimization is made. Loop ~i~ through the integers from ~2~ to ~\sqrt n~. If ~n~ is divisible by any of the values from ~2~ to ~\sqrt n~, the integer is not prime. The for-loop now has a time complexity of ~\mathcal O(\sqrt n)~ instead of ~\mathcal O(n)~.
This gives us an ~\mathcal O (TN\sqrt N)~ algorithm.