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

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