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)