C++算法计算多个数字的最小公倍数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4229870/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ algorithm to calculate least common multiple for multiple numbers
提问by Askener
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)?
是否有 C++ 算法来计算多个数字的最小公倍数，例如lcm(3,6,12)或lcm(5,7,9,12)？
回答by Blastfurnace
You can use std::accumulate and some helper functions:
您可以使用 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';
}
回答by Vladimir
回答by Steve314
The algorithm isn't specific to C++. AFAIK, there's no standard library function.
该算法并非特定于 C++。AFAIK，没有标准的库函数。
To calculate the LCM, you first calculate the GCD (Greatest Common Divisor) using Euclids algorithm.
要计算 LCM，首先要使用 Euclids 算法计算 GCD（最大公约数）。
http://en.wikipedia.org/wiki/Greatest_common_divisor
http://en.wikipedia.org/wiki/Greatest_common_divisor
The GCD algorithm is normally given for two parameters, but...
GCD 算法通常针对两个参数给出，但是...
GCD (a, b, c) = GCD (a, GCD (b, c))
= GCD (b, GCD (a, c))
= GCD (c, GCD (a, b))
= ...
To calculate the LCM, use...
要计算 LCM，请使用...
a * b
LCM (a, b) = ----------
GCD (a, b)
The logic for that is based on prime factorization. The more general form (more than two variables) is...
其逻辑基于素数分解。更一般的形式（两个以上的变量）是...
a b
LCM (a, b, ...) = GCD (a, b, ...) * --------------- * --------------- * ...
GCD (a, b, ...) GCD (a, b, ...)
EDIT - actually, I think that last bit may be wrong. The first LCM (for two parameters) is right, though.
编辑 - 实际上，我认为最后一点可能是错误的。不过，第一个 LCM（用于两个参数）是正确的。
回答by dividedbyzero
Using GCC with C++14 following code worked for me:
使用 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);
});
In C++17 there is std::lcm function (http://en.cppreference.com/w/cpp/numeric/lcm) that could be used in accumulate directly.
在 C++17 中有 std::lcm 函数（http://en.cppreference.com/w/cpp/numeric/lcm）可以直接用于累加。
回答by smac89
As of C++17, you can use std::lcm.
从 C++17 开始，您可以使用std::lcm.
And here is a little program that shows how to specialize it for multiple parameters
这是一个小程序，展示了如何将它专门用于多个参数
#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;
}
See it in action here: https://wandbox.org/permlink/25jVinGytpvPaS4v
在这里查看它的实际效果：https: //wandbox.org/permlink/25jVinGytpvPaS4v
回答by TheHaris
I just created gcd for multiple numbers:
我刚刚为多个数字创建了 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.
dbd-gcd。
n - number of numbers.
n - 数字的数量。
回答by John Dibling
Not built in to the standard library. You need to either build it yourself or get a library that did it. I bet Boost has one...
没有内置到标准库中。您需要自己构建它或获得一个这样做的库。我打赌 Boost 有一个...
回答by yayay
/*
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;
}
回答by portforwardpodcast
You can calculate LCM and or GCM in boost like this:
您可以像这样在 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;
}
(Example taken from http://www.boost.org/doc/libs/1_31_0/libs/math/doc/common_factor.html)
（示例取自http://www.boost.org/doc/libs/1_31_0/libs/math/doc/common_factor.html）
回答by user3166642
The Codes given above only discusses about evaluating LCM for multiple numbers however it is very likely to happen that while performing multiplications we mayoverflowinteger limit for data type storage
上面给出的代码只讨论了评估多个数字的 LCM，但是很可能发生在执行乘法时我们可能会溢出数据类型存储的整数限制
*A Corner Case :- *
*角落案例：- *
e.g. if while evaluating you reach situation such that if LCM_till_now=1000000000000000 next_number_in_list=99999999999999 and Hence GCD=1 (as both of them are relatively co-prime to each other)
例如，如果在评估时遇到这样的情况，如果 LCM_till_now=10000000000000000 next_number_in_list=99999999999999 并且因此 GCD=1 （因为它们彼此相对互质）
So if u perform operation (LCM_till_now*next_number_in_list) will not even fit in "unsigned long long int"
因此，如果您执行操作 (LCM_till_now*next_number_in_list) 甚至不适合“unsigned long long int”
Remedy :- 1.Use Big Integer Class 2.Or if the problem is asking for LCM%MOD----------->then apply properties of modular arithmetic.
补救措施：- 1.使用Big Integer Class 2.或者如果问题是要求LCM%MOD----------->然后应用模算术的属性。
