GCD and LCM

GCD also called Greatest Commun Divisor is a basic algorithm created by Euclid (Mid 4th century BC - Mid 3rd century BC). LCM also called Lowest Commun Multiple is a basic algorithm also created bu Euclid and it's formula depends on GCD. Here's the formula : a*b/GCD(a,b).
Theoreme (Euclide's lemma) : Consider A and B two integers; if R is the rest of the euclideen division of A and B then GCD(A,B)=GCD(B,R).

Pseudo-code

GCD can be implemented in two different ways : recursive and iterative. I recommand the recursive solution because it is shorter.

GCD(a,b) {
    if b == 0 return a
    return GCD(b,a%b)
}

GCD(a,b) {
   while a != b {
      if a > b a -= b;
      else b -= a;
   }
   return a;
}

C++ code

In C++ there is a gcd() function and a lcm function (for those who are tired to do a multiplication and a division) in numeric. There is also a new gcd function but it requires C++17, it is called __gcd().

#include <iostream>
#include <numeric>
#include <algorithm>
using namespace std;

inline int GCD_1(int a, int b){
 if (b == 0) return a;
 return GCD_1(b,a%b);
}

inline int GCD_2(int a, int b){
 while (a != b){
  if (a > b) a -= b;
  else b -= a;
 }
 return a;
}

inline int GCD_3(int a, int b){
 return gcd(a,b);
}

int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);
 int a,b;
 cin >> a >> b;
 cout << "GCD 1,2,3 result : " << GCD_1(a,b);
 cout << ' ' << GCD_2(a,b) << ' ' << GCD_3(a,b) << '\n';
 cout << "LCM result : ";
        cout << a*b/GCD_1(a,b) << ' ' << lcm(a,b) << '\n';
 return 0;
}

Another technique is to use tie :

//Greatest common divisor, the way Euclid intended :

int gcd(int a, int b){

    while (b != 0){

        tie(a,b) = make_tuple(b , a%b);

    }

    return a;

}