[Deadbyte]

Algorithm Series - 2 | GCD and LCM

Greatest common divisor
The greatest common divisor (gcd) or Highest common factor ( HCF ) of two integers is the greatest (largest) number that divides both of the integers evenly. Euclid came up with the idea of GCDs.

Algorithm
The GCD of any two positive integers can be defined as a recursive function:

gcd(u,v) = { gcd(u,v mod v) if v > 0
gcd(u,v) = { u, if v = 0

Examples
The GCD of 20 and 12 is 4, since 4 times 5 equals 20 and 4 times 3 equals 12. You can notice 3 and 5 have no common factor, hence their GCD is 1.
The GCD of 81 and 21 is 3.

Code in C++

PHP Code


<?php 
int gcd(int a, int b)
{
    for (;;)
    {
        if (a == 0) return b;
        b %= a;
        if (b == 0) return a;
        a %= b;
    }
} 


Least common multiple
The least common multiple of two integers is the smallest positive integer between all the multiples of both. It is usually denoted by LCM(a, b). Likewise, the LCM of more than two integers is the smallest positive integer that is divisible by each of them.
The LCM is known in elementary arithmetic as the "least common denominator" (LCD) that must be calculated before fractions can be added, subtracted or compared.

Algorithm
GCD(a,b) * LCM(a,b) = |a*b|
This formula is often used to compute the LCD, once known the GCD of a and b.

Code in C++

PHP Code


<?php 
int lcm(int a, int b)
{
    int temp = gcd(a, b);

    return temp ? (a / temp * b) : 0;
} 


Notice:
The algorithms that I am introducing in the series are simplistic some inefficient and slow but the series are for educational purpose for beginners in competitive programming.