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$ ~a^2-b^2~ is a difference of squares. This means it can be rewritten as $(a-b)(a+b)$ ~(a-b)(a+b)~.

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

Thus, we can check if $a+b$ ~a+b~ is prime to determine if $a^2-b^2$ ~a^2-b^2~ is prime. To check if $a+b$ ~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})$ ~\mathcal{O}(\sqrt{a+b})~

Comments

There are no comments at the moment.