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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Note that is a difference of squares. This means it can be rewritten as .
From this, it can be proven that is only prime when and is a prime.
Thus, we can check if is prime to determine if is prime. To check if 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:
Comments