Tsurupeta Tsurupeta - 1 month ago 11
C Question

Check whether or not a number is the sum of two squares in C

I need your help on this problem , I've been trying to solve it all day but I can't reach a solution.
I just started studying C so I apologize if it is a stupid question, however
I am only allowed to use:


  • if

  • for

  • do-while

  • while



statements to solve the problem.

I need to check whether or not a given number can be written as the sum of two squares, I do not need to know which are these two squares, and I do not need to analyze cases when the number is 0 or 1. What I've managed to build till now is:

unsigned int x;
unsigned int q = 1;
printf("Enter a number : \n");
scanf("%u", &x);
unsigned int j = sqrt(x - (q*q));
if (x != 1 && x != 0)
for (q; (q*q) <= (x/2); q++)
if ((x - (q*q)) == (j*j))
printf("Given number is sum of two squares");


This one sometimes works and sometimes doesn't, for example it does work for
65 (8^2+1^2)
and
90 (9^2+3^2)
but wouldn't work when I put 181
(10^2+9^2)
and so on..
Do you have any idea how I can fix this?

Answer

Ok, so here's a pseudo code for a possible solution:

Input x;

int a;
int b;

for(a=0; a <= x; a++){

   for(b=a; b <= x; b++){

      if((a*a + b*b) == x){
         Output is_solution;
      }

   }

}

In the nested loop, b is assigned the value of a to avoid checking the same sum of squares more than once.

Converting this to C, should look like this:

unsigned int x;
unsigned int a;
unsigned int b;
unsigned int is_solution = 0;

printf("Enter a number : \n");
scanf("%u", &x);

for(a=0; a<=x; a++){
   for(b=a; b<=x; b++){
      if((a*a + b*b) == x){
         printf("Given number is sum of two squares");
      }
   }
}

I'm a bit rusted in C, hopefully it doesn't have any nasty errors.

Comments