The functions in this tip find the greatest common divisor (GCD) or the least common multiple (LCM) of two given integers.
- Getting the GCD through recursion:
int GCD(int x,int y) { if(y==0) // base case, the programs stops if y reaches 0. return x; //it returns the GCD else return GCD(y,x%y); //if y doesn't reach 0 then recursion continues }
Suppose x=80 and y=100:
x y------------- 80 100 100 20 20 0
The GCD function shown above returns 20 as the GCD of the two given integers.
- Getting the GCD through iteration:
- Using the While Loop:
int GCD(int x,int y) { int t; while (y!=0) { t=y; y=x%y; x=t; } return x; }
Suppose x=80 and y=100:
x y t ----------------------- 80 100 20100 20 0 20 0
Then x=20 and the GCD of 80 and 100 is 20.
- Using the For Loop:
int GCD(int x,int y) { int i; if(x<y) { for(i=x;i>=0;i--) { if(x%i==0 &&y%i==0) {return i;} } } else { for(i=y;i>=0;i--) { if(x%i==0 && y%i==0) {return i;} } } return i; }
Suppose x=80 and y=100:
x y i ----------------------- 80 100 79 80 100 78 80 100 77| 80 100 2080%20==0 && 100%20==0
Then 20 is the GCD.
- Using the While Loop:
- Getting the LCM through recursion:
int LCM(int x,int y) { int prod; if(y%x==0) return y; else { prod=x*y; while(x!=y) // get the GCD of 2 given integers { if(x>y) x=x-y; else y=y-x; //x now is the GCD } return LCM(y,prod/x); //recurse, changing x to y and vice versa } //LCM = (x*y)/(GCD) }
Suppose x=80 and y=100:
x y prod GCD(x)---------------------------------80 100 800 80 2060 2040 2020 20 20800 / 20 = 400
Therefore, the LCM is 400.
- Getting LCM through iteration:
- Using the While Loop:
int LCM(int x,int y) { int i; i=y; while(y%x!=0) y=y+i; return y; }
Suppose x=80 and y=100:
x y i ------------------------80 100 100 80 200 10080 300 10080 400 100400 % 80 = 0
Then 400 is the LCM.
- Using the For Loop:
int LCM(int x,int y) { int i; if (x>ly) for(i=x;i<=x*y;i++) { if (i%x==0 && i%y==0) return i; } else for(i=y;i<=x*y;i++) { if (i%x==0 && i%y==0) return i; } return i; }
Suppose x=80 and y=100:
x y i ------------------------80 100 100 80 100 10180 100 102|80 100 400 400 % 80 == 0 && 400 % 100 == 0
Then 400 is the LCM.
- Using the While Loop: