Least common multiple

The least common multiple of positive integers n_{1},\\; n_{2},\\; n_{3}, \\cdots,\\; n_{i} is a number, which is is a multiple of all given integers and is minimal. We denote the least common multiple of numbers n_{1},\\; n_{2},\\; n_{3}, \\cdots,\\; n_{i} as


lcm(n_{1},\\; n_{2},\\; n_{3}, \\cdots,\\; n_{i})

Computing the least common multiple

Prime factorization

The easiest way to get the least common multiple of numbers n_{1},\\; n_{2},\\; n_{3}, \\cdots,\\; n_{i} is to express them as a product of prime numbers (factorize them). If we multiply together all prime numbers used in these products in their highest power, we get the least common multiple.

Example

Find the least common multiple of 6, 8, 15.

6 = 2 \\cdot 3 = 2^1  \\cdot  3^{1}
8 = 2\\cdot 2 \\cdot 2 = 2^{3}
15 = 5 \\cdot 3 = 5^{1} \\cdot 3^{1}
lcm(6,\\; 8,\\; 15) = 2^{3} \\cdot 3^{1} \\cdot 5 = 2 \\cdot 2 \\cdot 2 \\cdot 3 \\cdot 5 = 120

Example

Find the least common multiple of 140 and 17.

140 = 2\\cdot 2\\cdot 7\\cdot 5 = 2^{2}\\cdot 5^{1}\\cdot 7^{1}
72 = 2\\cdot 2\\cdot 2\\cdot 3\\cdot 3 = 2^{3}\\cdot 3^{2}
lcm(140,\\; 72) = 2^{3} \\cdot  3^{2} \\cdot  5^{1} \\cdot  7^{1} = 2\\cdot 2\\cdot 2\\cdot 3\\cdot 3\\cdot 5\\cdot 7 = 2520

Example

Find the least common multiple of 288 and 420?

288 = 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 3 \\cdot 3 = 2^{5} \\cdot 3^{2}
420 = 2 \\cdot 2 \\cdot 3 \\cdot 5 \\cdot 7 = 2^{2} \\cdot  3^{1} \\cdot  5^{1} \\cdot 7^{1}
lcm(288,\\; 420) = 2^{5} \\cdot 3^{2} \\cdot 5^{1} \\cdot 7^{1} = 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 2 \\cdot 3 \\cdot 3 \\cdot 5 \\cdot 7 = 10080

We can illustrate the above mentioned approach using the Venn's diagram. In the Venn's diagram the numbers 288 and 420 are represented as a sets of their prime factors. The factors, which they share in common, are placed in the intersection of these sets. Hence the diagram shows all prime factors of numbers 288 and 420 in their highest power – we can find their least common multiple by simply multiplying all displayed prime factors together.

The least common multiple using Venn's diagram
The least common multiple using Venn's diagram

Euclidean algorithm

Much more effective way to get the least common multiple of two numbers is to multiply them and divide the result by their greatest common divisor. The greatest common divisor may be computed by the Euclidean algorithm, which is very fast, because it does not require factorization of the given numbers.


lcm(n_{1},\\; n_{2}) = {{n_{1} \\cdot n_{2} } \\over {gcd(n_{1},\\; n_{2})} }

Example

gcd(140,\\; 72) = 4
lcm(140,\\; 72) = {{140 \\cdot 72} \\over {gcd(140,\\; 72)}} = {{10080} \\over {4}} = 2520

Code

    /**
     * Returns least common multiple of two numbers
     * @param a number 1
     * @param b number 2
     * @return lcm(a, b)
     */
    public static int lcm(int a, int b) {
        if (a == 0 || b == 0) {
            return 0;
        }
        return (a * b) / gcd(a, b);
    }

    /**
     * Returns greatest common divisor of the given numbers
     * @param a number 1
     * @param b number 2
     * @return gcd(a, b)
     */
    public static int gcd(int a, int b) {
        if (a < 1 || b < 1) {
            throw new IllegalArgumentException("a or b is less than 1");
        }
        int remainder = 0;
        do {
            remainder = a % b;
            a = b; 
            b = remainder;
        } while (b != 0);
        return a;
    }
/**
 * Least common multiple of numbers "a" and "b"
 * @param a number "a"
 * @param b number "b"
 * @return lcm(a, b)
 * @autor Thomas (www.adamjak.net)
 */
public static int lcm(int a, int b)
{
    if (a == 0 || b == 0)
    {
        return 0;
    }
    return (a * b) / gcd(a, b);
}

/**
 * Greatest common divisor of numbers "a" and "b"
 * @param a number "a"
 * @param b number  "b"
 * @return gcd(a, b)
 * @autor Thomas (www.adamjak.net)
 */
public static int gcd(int a, int b)
{
    if (a < 1 || b < 1)
    {
        throw new ArgumentException("a or b is less than 1");
    }
    int r = 0;
    do
    {
        r = a % b;
        a = b;
        b = r;
    } while (b != 0);
    return a;
}
/**
 * Least common multiple of numbers "a" and "b"
 * @param $a number "a"
 * @param $b number "b"
 * @return lcm(a, b)
 * @autor Thomas (www.adamjak.net)
 */
function lcm($a, $b) {
    if ($a == 0 || $b == 0) {
        return 0;
    }
    return ($a * $b) / gcd($a, $b);
}

/**
 * Least common multiple of numbers "a" and "b"
 * @param $a number "a"
 * @param $b number "b"
 * @return gcd(a, b)
 * @autor Thomas (www.adamjak.net)
 */
function gcd($a, $b) {
    if ($a < 1 || $b < 1) {
        die("a or b is less than 1");
    }
    $r = 0;
    do {
        $r = $a % $b;
        $a = $b;
        $b = $r;
    } while ($b != 0);
    return $a;
}

Sources

  • POLÁK, Josef. Přehled středoškolské matematiky. 8th edition. Praha 4 : Prometheus, 2005. 608 p.

www.EuAutodily.cz SEO od společnosti Digital Pylon


Online casino s algoritmem

České casino online online slot-vegas.cz





Zajímavé články: Jak najít práci snů? Zvolte kariéru v IT!, Češi mají rádi hrací automaty online, Jak funguje algoritmické obchodování Casino, Online výuka Algoritmus a online marketing mají svá pravidla, Automaty, Matematický vliv, Ratings, Jak fungují algoritmy hazardních her online: více znalostí, více peněz, SYPWAI - nástroj pro vědecký vývoj, Vynikají na globálním trhu: Nejlepší vývojáři softwaru pro online výherní automaty, Jak si vybrat nejlepší české online casino, Proč byste měli hrát online casino VPN revoluce, Kde najdeme algoritmy v každodenním životě?