在Stack Overflow上有许多关于如何找到两个值的最大公约数的问题。一个很好的答案展示了一个整洁的递归函数来完成这个任务。
但是，如何找到一组超过2个整数的最大公约数呢？我似乎找不到任何例子。
有人能否建议最有效的代码来实现此函数？
static int GCD(int[] IntegerSet)
{
// what goes here?
}
12个回答
52
以下是您从链接中获取的代码示例，使用LINQ和GCD方法。它使用其他答案中描述的理论算法... GCD(a, b, c) = GCD(GCD(a, b), c)
static int GCD(int[] numbers)
{
return numbers.Aggregate(GCD);
}
static int GCD(int a, int b)
{
return b == 0 ? a : GCD(b, a % b);
}
- Martin Jonáš
3
1一个小的优化：
return b == 0 ? a : GCD(Math.Min(a, b), Math.Max(a, b) % Math.Min(a, b));
当numbers[]包含升序值时，这可以节省高达50%的“%”操作。 - robert41@robert4 - 你的解决方案会出现除以零的错误。需要添加一个检查
a == 0 的条件。return b == 0 ? a : (a == 0 ? b : GCD(Math.Min(a,b), Math.Max(a,b) % Math.Min(a,b))); - NightOwl8881@NightOwl888 你说得有道理。
return (a == 0 || b == 0) ? a|b : GCD(Math.Min(a, b), Math.Max(a, b) % Math.Min(a, b)); - robert413
您可以使用GCD的常见属性：
GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b)
假设您已经定义了GCD(a, b)，那么很容易进行概括：
public class Program
{
static void Main()
{
Console.WriteLine(GCD(new[] { 10, 15, 30, 45 }));
}
static int GCD(int a, int b)
{
return b == 0 ? a : GCD(b, a % b);
}
static int GCD(int[] integerSet)
{
return integerSet.Aggregate(GCD);
}
}
- Darin Dimitrov
1
谢谢，正是我需要的，但你的编辑来得稍微有点晚了，Matajon在你之前给出了相同的答案...所以我认为公平的做法是接受他的回答。（无论如何+1） - BG100
3
这是C#版本。
如果您需要计算正整数的最大公约数，请参考此示例。
public static int Gcd(int[] x) {
if (x.length < 2) {
throw new ArgumentException("Do not use this method if there are less than two numbers.");
}
int tmp = Gcd(x[x.length - 1], x[x.length - 2]);
for (int i = x.length - 3; i >= 0; i--) {
if (x[i] < 0) {
throw new ArgumentException("Cannot compute the least common multiple of several numbers where one, at least, is negative.");
}
tmp = Gcd(tmp, x[i]);
}
return tmp;
}
public static int Gcd(int x1, int x2) {
if (x1 < 0 || x2 < 0) {
throw new ArgumentException("Cannot compute the GCD if one integer is negative.");
}
int a, b, g, z;
if (x1 > x2) {
a = x1;
b = x2;
} else {
a = x2;
b = x1;
}
if (b == 0) return 0;
g = b;
while (g != 0) {
z= a % g;
a = g;
g = z;
}
return a;
}
}
如果您需要计算正整数的最大公约数，请参考此示例。
- randomguy
3
我刚想提到你漏掉了第二个函数...但是你已经修复了 :) 谢谢，这正是我所需要的。 - BG100
我本来要接受你的答案，但是Darin Dimitrov和Matajon提出了更简洁的方法。抱歉！（无论如何+1） - BG100
1抱歉，我太匆忙了，认为只有我才有正确的答案。 ;) 如果速度很重要，应该对Darin和Matajon描述的LINQ方法进行测试。如果不是，我很乐意说您应该使用LINQ方法，因为它更加优雅。 - randomguy
3
维基百科:
最大公约数是一种可结合函数: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c).
三个数的最大公约数可以通过 gcd(a, b, c) = gcd(gcd(a, b), c) 的方式计算，或者应用交换律和结合律进行其他不同的方式。这可以扩展到任意数量的数字。
只需取前两个元素的最大公约数，然后计算结果和第三个元素的最大公约数，再计算结果和第四个元素的最大公约数...
- Landei
2
将此重写为单个函数...
static int GCD(params int[] numbers)
{
Func<int, int, int> gcd = null;
gcd = (a, b) => (b == 0 ? a : gcd(b, a % b));
return numbers.Aggregate(gcd);
}
- Jonathan Rose
1
int GCD(int a,int b){
return (!b) ? (a) : GCD(b, a%b);
}
void calc(a){
int gcd = a[0];
for(int i = 1 ; i < n;i++){
if(gcd == 1){
break;
}
gcd = GCD(gcd,a[i]);
}
}
- Jitendra
2
请在您的回答中添加一些解释。 - Alex Kulinkovich
当然可能需要更多的解释，但这是唯一的答案，其中gcd = 1，所以要赞扬。 - Cimbali
1
gcd(a1,a2,...,an)=gcd(a1,gcd(a2,gcd(a3...(gcd(a(n-1),an)))))，因此我会一步一步地执行它，如果某个gcd的值为1，则中止执行。
如果您的数组已排序，则更快地计算较小数字的gcd可能会更快，因为这样可能更有可能有一个gcd的值为1，从而可以停止计算。
- phimuemue
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);
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]));
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 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;
}
- yayay
0
let a = 3
let b = 9
func gcd(a:Int, b:Int) -> Int {
if a == b {
return a
}
else {
if a > b {
return gcd(a:a-b,b:b)
}
else {
return gcd(a:a,b:b-a)
}
}
}
print(gcd(a:a, b:b))
- user10111825
0
GCD(a, b, c) = GCD(a, GCD(b, c)) = GCD(GCD(a, b), c) = GCD(GCD(a, c), b)
最大公约数（a，b，c）= GCD（a，GCD（b，c））= GCD（GCD（a，b），c）= GCD（GCD（a，c），b）
public class Program {
static void Main() {
Console.WriteLine(GCD(new [] {
10,
15,
30,
45
}));
}
static int GCD(int a, int b) {
return b == 0 ? a : GCD(b, a % b);
}
static int GCD(int[] integerSet) {
return integerSet.Aggregate(GCD);
}
}
- Akshay Kolhapure
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接