Editorial for A Square Problem


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

Note that a^2-b^2 is a difference of squares. This means it can be rewritten as (a-b)(a+b).

From this, it can be proven that a^2-b^2 is only prime when a-b=1 and a+b is a prime.

Thus, we can check if a+b is prime to determine if a^2-b^2 is prime. To check if a+b is prime, we can check if it is divisible by any numbers less than its square root. The proof is left as an exercise for the reader.

Time Complexity: \mathcal{O}(\sqrt{a+b})


Comments

There are no comments at the moment.