This tutorial will show you how you can code functions to calculate the GCD, greatest common divisor, and LCM, lowest common multiple, of two integer values.
BUT the best part is the minimal coding required 
For example to make the GCD of 2 numbers, the easiest approach is to take the lowest of the 2 and decremented one at a time until it divides the both integers exactly. (preview below)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | int gcd_easy(int a, int b){ // a will hold the lower integer // b will be the larger integer if(a>b){ int t=a; a=b; b=t; } // now we shall find the gcd by checking the range [a..1) // for a number that divides 'a' and 'b' exactly for(int i=a; i>1; i--) if( !(a%i || b%i) ) return i; // we haven't found anyone so we return 1 return 1; } |
You can see that it’s a very easy task but this method involves WAY TOO MUCH calculations in big numbers.
So below you will find a solution that is way smaller and faster.
It’s the so-called Euclid method where you continuously get the MOD of “two numbers” till its zero and the GCD is the previous MOD found. The two numbers are a and b at the start but then a becomes previous b and b becomes previous MOD.
For example: a=120 b=22
Step 1: 120 % 22 = 10
Step 2: 22 % 10 = 2
Step 3: 10 % 2 = 0
So our result is previous MOD which equals 2
Now we should see the code for this function which is annoyingly small:
1 2 3 4 | int gcd(int a, int b){ if(b==0) return a; return gcd(b,a%b); } |
Exactly as described 
Easy, Small, Fast and Accurate !!!
Now for the LCM, lowest common multiple, we just have to find the GCD of the two numbers multiplication. So it is not difficult to make the function:
1 2 3 | int lcm(int a, int b){ return a*b/gcd(a,b); } |
I know it’s a task very easy to implement and think of yourself but a faster and smaller method is always more attractive. I hope you liked my tutorial, stay tuned for the next one.
For any code problems or suggestions or even a better solution just comment below.
