26

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

4

16 回答 16

50

您可以使用 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';
}
于 2010-11-19T22:25:50.573 回答
18

boost 提供了计算 2 个数字的 lcm 的函数（见这里）

然后使用以下事实

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

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

于 2010-11-19T22:17:44.777 回答
6

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

要计算 LCM，首先使用 Euclids 算法计算 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（用于两个参数）是正确的。

于 2010-11-19T22:30:00.463 回答
6

从 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

于 2017-11-25T17:10:55.447 回答
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）可以直接用于累积。

于 2016-12-16T13:37:02.957 回答
1

未内置到标准库中。您需要自己构建它或获取一个库来完成它。我敢打赌Boost有一个...

于 2010-11-19T22:17:23.240 回答
1

我刚刚为多个数字创建了 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 - 数字的数量。

于 2012-12-01T17:55:09.827 回答
0

I found this while searching a similar problem and wanted to contribute what I came up with for two numbers.

#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;
}
于 2014-09-30T02:26:04.477 回答
0 
/*

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

源代码参考

于 2012-11-05T21:10:12.947 回答
0

您可以像这样在 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）

于 2013-10-31T23:48:27.617 回答
0

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

*一个角落案例：- *

例如，如果在评估您达到的情况时，如果 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-----------> 然后应用模运算的属性。

于 2014-07-05T21:22:39.520 回答
0

利用 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();
于 2015-11-14T09:36:47.980 回答
0 
#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;
    }
}
于 2021-04-29T18:02:53.447 回答
-1
  • let the set of numbers whose lcm you wish to calculate be theta
  • let i, the multiplier, be = 1
  • let x = the largest number in theta
  • x * i
  • if for every element j in theta, (x*i)%j=0 then x*i is the least LCM
  • if not, loop, and increment i by 1
于 2013-10-01T06:34:25.690 回答
-1

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

请注意，我并不是说它是有效的或任何东西，但它在概念上确实可以扩展到多个数字。在找到 LCM 之前，您只需要空间来跟踪您的原始数字和您操作的克隆集。

于 2010-11-19T22:28:44.660 回答
-1 
#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();
}
于 2011-02-06T03:24:09.260 回答