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, we can loop from i = 2 to i = \sqrt x, and check if x is divisible by any i. If it is divisible, then 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 is a good number.

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

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


Comments

There are no comments at the moment.