Fermart’s Theorm(페르마의 정리)

This approach is based on the following statement, which is based on Fermat’s Theorem:

Any positive number nnn is expressible as a sum of two squares if and only if the prime factorization of nnn, every prime of the form (4k+3)(4k+3)(4k+3) occurs an even number of times.

By making use of the above theorem, we can directly find out if the given number ccc can be expressed as a sum of two squares.

To do so we simply find all the prime factors of the given number ccc, which could range from [2,c][2,\sqrt{c}][2, c ​ ] along with the count of those factors, by repeated division. If at any step, we find out that the number of occurrences of any prime factor of the form (4k+3)(4k+3)(4k+3) occurs an odd number of times, we can return a False value.

In case, ccc itself is a prime number, it won’t be divisible by any of the primes in the [2,c][2,\sqrt{c}][2, c ​ ]. Thus, we need to check if ccc can be expressed in the form of 4k+34k+34k+3. If so, we need to return a False value, indicating that this prime occurs an odd number(1) of times.

Otherwise, we can return a True value.