Editorial for GlobeX Cup '18 J3 - Good Numbers - Olympiads Online Judge

Editorial for GlobeX Cup '18 J3 - Good Numbers

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: Ninjaclasher

For each integer, $x$ ~x~, we can loop from $i = 2$ ~i = 2~ to $i = \sqrt x$ ~i = \sqrt x~, and check if $x$ ~x~ is divisible by any $i$ ~i~. If it is divisible, then $x$ ~x~ is not a prime. Otherwise, it is.

We can then sum up the digits, and perform the same prime checking.

If both checks are satisfied, then $x$ ~x~ is a good number.

Be wary of $x = 1$ ~x = 1~, as $1$ ~1~ is not a prime.

Time Complexity: $\mathcal{O}(N \sqrt{\max x})$ ~\mathcal{O}(N \sqrt{\max x})~

Comments

There are no comments at the moment.