Given a number, we have to find out the number ways to express it in the form of sum of two integer squares.

For example let us consider 25, it can be written as sum of the pairs (0,25) (9,16)

24 cannot be written as a sum of any two squares.

Mathematically this problem is to find the roots of the equation x

The algorithm for this problem is simple. let us start i with 0 and check if (n-i*i)

Take the example of 25, Here is the trace of the algorithm

For example let us consider 25, it can be written as sum of the pairs (0,25) (9,16)

24 cannot be written as a sum of any two squares.

Mathematically this problem is to find the roots of the equation x

^{2}+y^{2}-n = 0 where n is given.The algorithm for this problem is simple. let us start i with 0 and check if (n-i*i)

*is a perfect square*. We repeat this process until (n-i*i) is greater than i*iTake the example of 25, Here is the trace of the algorithm

i n-i*i Result

—————————–

0 25 – Yes

1 24 – No

2 21 – No

3 16 – Yes

4 9 – break

Here is the C++ code to do this.