Editorial for CCC '19 S2 - Pretty Average Primes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: KevinLu

For this problem, we can use a simple for-loop to generate values of $a$ ~a~ and $b$ ~b~.

Set $a = i$ ~a = i~ and $b = 2n - i$ ~b = 2n - i~. Loop $i$ ~i~ through the integers from $2$ ~2~ to $2n$ ~2n~.

Check if they are both prime and that $2n$ ~2n~ is equal to $a + b$ ~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$ ~i~ through the integers from $2$ ~2~ to $n$ ~n~ when checking if the integer is prime. If $n$ ~n~ is divisible by any of the values from $2$ ~2~ to $n$ ~n~, the integer is not prime.

This gives us an $\mathcal O(TN^2)$ ~\mathcal O(TN^2)~ algorithm.

For subtask 2, an optimization is made. Loop $i$ ~i~ through the integers from $2$ ~2~ to $\sqrt n$ ~\sqrt n~. If $n$ ~n~ is divisible by any of the values from $2$ ~2~ to $\sqrt n$ ~\sqrt n~, the integer is not prime. The for-loop now has a time complexity of $\mathcal O(\sqrt n)$ ~\mathcal O(\sqrt n)~ instead of $\mathcal O(n)$ ~\mathcal O(n)~.

This gives us an $\mathcal O(TN \sqrt N)$ ~\mathcal O(TN \sqrt N)~ algorithm.

Comments

There are no comments at the moment.