Given integer n decide if it is possible to represent it.SPOJ Prob. 91 as a sum of two squares of integers.

In number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as
x^2+y^2=c
with x and y integers, if and only if

For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:

On the other hand, the primes 3, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them can be expressed as the sum of two squares.

More Info http://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares


I used Above Fact to Solve the Question(to Solve SPOJ problem You have to Modify the program )

#include
#include

int isSquare(int c)
{
int a=0;int b=sqrt(c);
if(c%4==1)//remove this to solve spoj probelm
{
while(a<=sqrt(c))
{ int pows=pow(a,2)+pow(b,2);
if(a!=b && pows==c ) //a!=b means 1^1+1^1=2 not allowed
{ printf(" yes Possible \t %d %d ", a,b);
return 1;
}
else if(pows a++;
else b--;

printf( " %d %d %d \n", a,b,pows);
}

}
else
{ printf( "not Possible");
return 0;
}
return 0;
}

int main()
{
printf(" %d ", isSquare(29));
}


TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/nLGDs