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.