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 提供了计算 2 个数字的 lcm 的函数（请参见此处）

事实

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

然后利用您也可以轻松计算多个数字的 lcm 的

Answer 3

从 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 4

该算法并非特定于 C++。 AFAIK，没有标准库函数。

要计算 LCM，首先使用欧几里得算法计算 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 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 有一个...

Answer 7

我刚刚为多个数字创建了 gcd：

#include <iostream>    
using namespace std;
int dbd(int n, int k, int y = 0);
int main()
{
    int h = 0, n, s;
    cin >> n;
    s = dbd(n, h);
    cout << s;
}

int dbd(int n, int k, int y){
        int d, x, h;
        cin >> x;
        while(x != y){
            if(y == 0){
                break;
            }
            if( x > y){
                x = x - y;
            }else{
                y = y - x;
            }
        }
        d = x;
        k++;
        if(k != n){
        d = dbd(n, k, x);
        }
    return d;
}

dbd - gcd。

n - 数字的数量。

Answer 8

/*

Copyright (c) 2011, Louis-Philippe Lessard
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

*/

unsigned gcd ( unsigned a, unsigned b );
unsigned gcd_arr(unsigned * n, unsigned size);
unsigned lcm(unsigned a, unsigned b);
unsigned lcm_arr(unsigned * n, unsigned size);
int main()
{
    unsigned test1[] = {8, 9, 12, 13, 39, 7, 16, 24, 26, 15};
    unsigned test2[] = {2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048};
    unsigned result;

    result = gcd_arr(test1, sizeof(test1) / sizeof(test1[0]));
    result = gcd_arr(test2, sizeof(test2) / sizeof(test2[0]));
    result = lcm_arr(test1, sizeof(test1) / sizeof(test1[0]));
    result = lcm_arr(test2, sizeof(test2) / sizeof(test2[0]));

    return result;
}


/**
* Find the greatest common divisor of 2 numbers
* See http://en.wikipedia.org/wiki/Greatest_common_divisor
*
* @param[in] a First number
* @param[in] b Second number
* @return greatest common divisor
*/
unsigned gcd ( unsigned a, unsigned b )
{
    unsigned c;
    while ( a != 0 )
    {
        c = a;
        a = b%a;
        b = c;
    }
    return b;
}

/**
* Find the least common multiple of 2 numbers
* See http://en.wikipedia.org/wiki/Least_common_multiple
*
* @param[in] a First number
* @param[in] b Second number
* @return least common multiple
*/
unsigned lcm(unsigned a, unsigned b)
{
    return (b / gcd(a, b) ) * a;
}

/**
* Find the greatest common divisor of an array of numbers
* See http://en.wikipedia.org/wiki/Greatest_common_divisor
*
* @param[in] n Pointer to an array of number
* @param[in] size Size of the array
* @return greatest common divisor
*/
unsigned gcd_arr(unsigned * n, unsigned size)
{
    unsigned last_gcd, i;
    if(size < 2) return 0;

    last_gcd = gcd(n[0], n[1]);

    for(i=2; i < size; i++)
    {
        last_gcd = gcd(last_gcd, n[i]);
    }

    return last_gcd;
}

/**
* Find the least common multiple of an array of numbers
* See http://en.wikipedia.org/wiki/Least_common_multiple
*
* @param[in] n Pointer to an array of number
* @param[in] size Size of the array
* @return least common multiple
*/
unsigned lcm_arr(unsigned * n, unsigned size)
{
    unsigned last_lcm, i;

    if(size < 2) return 0;

    last_lcm = lcm(n[0], n[1]);

    for(i=2; i < size; i++)
    {
        last_lcm = lcm(last_lcm, n[i]);
    }

    return last_lcm;
}

源代码参考

Answer 9

您可以在 boost 中计算 LCM 和/或 GCM，如下所示：（

#include <boost/math/common_factor.hpp>
#include <algorithm>
#include <iterator>


int main()
{
    using std::cout;
    using std::endl;

    cout << "The GCD and LCM of 6 and 15 are "
     << boost::math::gcd(6, 15) << " and "
     << boost::math::lcm(6, 15) << ", respectively."
     << endl;

    cout << "The GCD and LCM of 8 and 9 are "
     << boost::math::static_gcd<8, 9>::value
     << " and "
     << boost::math::static_lcm<8, 9>::value
     << ", respectively." << endl;
}

示例取自 http://www.boost.org/doc/libs/1_31_0/libs/math/doc/common_factor.html)

Answer 10

上面给出的代码仅讨论了如何评估多个数字的 LCM，但是很可能发生在执行乘法时溢出数据类型存储的整数限制< /strong>

*极端情况 :- *

例如
如果在评估时达到这样的情况，如果 LCM_till_now=1000000000000000 next_number_in_list=99999999999999 且因此 GCD=1 （因为它们彼此相对互质）

所以如果你执行操作 (LCM_till_now*next_number_in_list) 甚至不适合“ unsigned long long int”

补救措施：-
1.使用大整数类
2.或者如果问题要求 LCM%MOD------------> 然后应用模运算的属性。

Answer 11

利用 lcm 应该可整除的事实
由列表中的所有数字组成。这里的列表是一个包含数字的向量

        int lcm=*(len.begin());
    int ini=lcm;
    int val;
    int i=1;
    for(it=len.begin()+1;it!=len.end();it++)
    {
        val=*it;
        while(lcm%(val)!=0)
        {
            lcm+=ini;
        }
        ini=lcm;
    }
    printf("%llu\n",lcm);
    len.clear();

Answer 12

我在搜索类似问题时发现了这一点，并想贡献我对两个数字的想法。

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

int main()
{
    cin >> x >> y;

    // zero is not a common multiple so error out
    if (x * y == 0)
        return -1;

    int n = min(x, y);
    while (max(x, y) % n)
        n--;

    cout << n << endl;
}

Answer 13

#include<iostream>
using namespace std;

int lcm(int, int, int); 

int main()
{
    int a, b, c, ans;
    cout<<"Enter the numbers to find its LCM"<<endl; //NOTE: LCM can be found only for non zero numbers. 
    cout<<"A = "; cin>>a;
    cout<<"B = "; cin>>b;
    cout<<"C = "; cin>>c; 
    ans = lcm(a,b,c);
    cout<<"LCM of A B and C is "<<ans;
}

int lcm(int a, int b, int c){
    static int i=1;

    if(i%a == 0 && i%b == 0 && i%c ==0){  //this can be altered according to the number of parameters required i.e this is for three inputs
        return i;
    } else {
        i++;
        lcm(a,b,c);
        return i;
    }
}

Answer 14

如果您查看此页面，您可以看到一个相当简单的您可以使用的算法。 :-)

我并不是说它很高效或者什么，但它在概念上确实可以扩展到多个数字。您只需要空间来跟踪原始数字和您操作的克隆集，直到找到 LCM。

Answer 15

#include
#include

void main()
{
    clrscr();

    int x,y,gcd=1;

    cout<>x;

    cout<>y;

    for(int i=1;i<1000;++i)
    {
        if((x%i==0)&&(y%i==0))
        gcd=i;
    }

    cout<<"\n\n\nGCD :"<
    cout<<"\n\n\nLCM :"<<(x*y)/gcd;

    getch();
}

Answer 16

• 令要计算 lcm 的数字集合为 theta
• 让 i，乘数 be = 1
• 让 x = theta 中最大的数
• x * i
• 如果对于 theta 中的每个元素 j，(x*i)%j=0那么 x*i 是最小的 LCM
• 如果不是，则循环，并将 i 加 1