C++ algorithm to calculate least common multiple for multiple numbers

Askener picture Askener · Nov 19, 2010 · Viewed 84.4k times · Source

Is there a C++ algorithm to calculate the least common multiple for multiple numbers, like lcm(3,6,12) or lcm(5,7,9,12)?

Answer

Blastfurnace picture Blastfurnace · Nov 19, 2010

You can use std::accumulate and some helper functions:

#include <iostream>
#include <numeric>

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

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

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

int main()
{
    int arr[] = { 5, 7, 9, 12 };

    int result = std::accumulate(arr, arr + 4, 1, lcm);

    std::cout << result << '\n';
}