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 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.


Comments

There are no comments at the moment.