OJ Board

How to check if given integer n can be represented as sum of two squares of integers??
I know that:
a)Those numbers n whose prime divisors of the form 4*m+3 divide n an even number of times can be written as the sum of two squares.
b)Jacobi's Two Square Theorem: The number of representations of a positive integer as the sum of two squares is equal to four times the difference of the numbers of divisors congruent to 1 and 3 modulo 4.

But when n is big (10^10 or 10^12) it's hard to check all divisors or find all prime divisors of the form 4*m+3.

Can anyone give me a hint how to efficently check whether n can be represented as the sum of two squares or not??

Finding all prime factors of the form 4m+3 works pretty fast even for the numbers like 10^12. If you find all prime numbers not greater than sqrt(n) first, you only have to check pi(sqrt(n)) factors for given number later (where pi(x) denotes the count of prime numbers not greater than x).

For example if n=10^12 => sqrt(n) = 10^6 => pi(sqrt(n)) = 78000 (aprox.).
The last number is not so big and thus you can check at most 78000 prime numbers (of course you can break checking if given prime factor is congruent to 3 modulo 4 and it hasn't got an even exponent).