C++算法计算多个数的最小公倍数

Question

是否有C++算法来计算多个数字的最小公倍数,如lcm(3,6,12)或lcm(5,7,9,12)？

Answer 1

您可以使用std :: accumulate和一些辅助函数:

#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';
}

Answer 2

boost提供计算lcm的2个数字的函数(见这里)

然后使用这个事实

lcm(a,b,c) = lcm(lcm(a,b),c)

您也可以轻松计算多个数字的lcm

Answer 3

该算法不是特定于C++的.AFAIK,没有标准的库函数.

要计算最小公倍数,首先使用欧几里德算法计算GCD(最大公约数).

http://en.wikipedia.org/wiki/Greatest_common_divisor

GCD算法通常给出两个参数,但......

GCD (a, b, c) = GCD (a, GCD (b, c))
              = GCD (b, GCD (a, c))
              = GCD (c, GCD (a, b))
              = ...

要计算LCM,请使用......

                a * b
LCM (a, b) = ----------
             GCD (a, b)

其逻辑基于素数因子分解.更一般的形式(超过两个变量)是......

                                          a                 b        
LCM (a, b, ...) = GCD (a, b, ...) * --------------- * --------------- * ...
                                    GCD (a, b, ...)   GCD (a, b, ...)

编辑 - 实际上,我认为最后一点可能是错误的.但是,第一个LCM(两个参数)是正确的.

Answer 4

从 C++17 开始，您可以使用std::lcm.

这是一个小程序，展示了如何将它专门用于多个参数

#include <numeric>
#include <iostream>

namespace math {

    template <typename M, typename N>
    constexpr auto lcm(const M& m, const N& n) {
        return std::lcm(m, n);
    }

    template <typename M, typename ...Rest>
    constexpr auto lcm(const M& first, const Rest&... rest) {
        return std::lcm(first, lcm(rest...));
    }
}

auto main() -> int {
    std::cout << math::lcm(3, 6, 12, 36) << std::endl;
    return 0;
}

在这里查看它的实际效果：https : //wandbox.org/permlink/25jVinGytpvPaS4v

Answer 5

使用 GCC 和 C++14 以下代码对我有用：

#include <algorithm>
#include <vector>

std::vector<int> v{4, 6, 10};    
auto lcm = std::accumulate(v.begin(), v.end(), 1, [](auto & a, auto & b) {
    return abs(a * b) / std::__gcd(a, b);
});

在 C++17 中有 std::lcm 函数（http://en.cppreference.com/w/cpp/numeric/lcm）可以直接用于累加。

Answer 6

未内置于标准库中。您需要自己构建它，或者获得一个可以完成它的库。我敢打赌 Boost 有一个...