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 x2+y2-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*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 x2+y2-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*i
Take 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.