Question

Can someone explain this c++ program to me, especially the part in finding the GCD? Thank you.
#include #include #include int main() { int a = 0; int b = 0; clrscr(); cout << "Enter First Number: "; cin >> a; cout << "Enter Second Number: "; cin >> b; cout<<"\n\n"; if((a<=0)||(b<=0)) exit(1); int c = 0; int d = 1; int gcd = 0, lcm; if(a >= b){c = a;} if(b > a){c = b;} while(d <= c/2) { if(a%d==0 && b%d==0){gcd = d;} ++d; } cout << "GCD is "< 13 years ago

Answer 1

int c = 0;
int d = 1;
int gcd = 0, lcm;
if(a >= b){c = a;}
if(b > a){c = b;}
while(d <= c/2)
{
if(a%d==0 && b%d==0){gcd = d;}
++d;
}

it is computing the gcd of two input numbers by brute force :
by checking every number from "1" to "half of biggest of the two input numbers"
checking to see, if it is divisible by both "a" and "b"

Answer 2

Hi ganeshie8, don't you think the while condition could work checking from "1" to "half of lowest of the two input numbers" ?

Answer 3

it wont work.
test with input and see : (2, 100)

GCD of of two numbers can be lowest input number itself, as well. so checking till "half of lowest of input numbers" wont give the exact answer.. hope its clear nw...

good observation btw :)

Answer 4

clear, thanks for explaining; so may be till "lowest of input numbers" could work ?

Answer 5

yw..
that works.. hmm it may iterate more times if the lowest number is not really that low.
ex: 98, 100
it iterates 98 times, instead of 100/2 times.

but on the other hand, with our current approach. it loops too many times if the number is very low...
ex: 2, 100
it keeps iterating 100/2 times...

so both are equally bad !!

Answer 6

ok, thank you

Answer 7

yw... :)

Answer 8

Thank you!