Algorithm to find other two sides of a trianlge when one side is given [duplicate]

Question

This question already has answers here:

Algorithm to determine whether a given number N can become hypotenuse of right triangle with all 3 integral sides (5 answers)

Closed 8 years ago.

There is a triangle, and its hypotenuse length is given to us. Now our task is to find whether other two sides are also integer or not.

For above question, I build one code, but that is inefficient, can you suggest any efficient algorithm for the same.

My work

#include<stdio.h>
#include<cmath>

using namespace std;

int isInt(double x) {
    if( (x - (int)x) == 0 ) return 1;
    return 0;
}

main() {
    int S;
    int flag = 0;

    scanf("%d", &S);
    flag = 0;
    for(int i = 1; i < S; i++) {
       if( isInt(sqrt(S*S - i*i)) ) {
           printf("EXIST\n");
           flag = 1;
           break;
        }
    }
    if(!flag) printf("NOT EXIST\n");
    return 0;
}

Answer 1

If I understand you correctly, you are trying to answer the question "Does an integer sized right triangle with hypothenuse S exist?".

Immediate improvements to your method:

• Loop i from 1 to S/2 instead of 1 to S-1.
  • Actually, S/2 itself is not necessary either, since that would imply a==b, and c must therefore contain an odd number of sqrt(2)-factors.
• (No need to set flag=0 twice.)

Instead of checking for integer square roots (sqrt operation is time consuming), you could use this alternative integer-only variant:

int check(int c){
  int a=1;
  int b=c-1;
  int cc=c*c;
  while(a<b){
    int sum=a*a+b*b;
    if(sum==cc) return true;
    if(sum<cc){
      a++;
    }else{
      b--;
    }
  }
  return false;
}

(code not tested.)

There are other ways to answer the question involving theorems for expressibility as the sum of two squares applied to the square of the given hypothenuse. However, these generally involve factorization, which is also a hard problem.

(edit: removed wrong statement regarding factorization complexity)

Further info:

http://en.wikipedia.org/wiki/Pythagorean_triple http://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares

(see comments, I'm not allowed to post enough links)