C++求最大公约数算法实现

小蓝 • 2024-12-05 10:22 • 编程

一、什么是最大公约数

在数学中，最大公约数，简称为gcd，又称最大公因数、最大公因子，指两个或多个整数共有约数中最大的一个。

例如，12和16的最大公约数是4，一般表示为gcd(12, 16) = 4。

二、求最大公约数的几种方法

目前求最大公约数的方法主要有以下几种：

欧几里得算法

欧几里得算法，又称辗转相除法，是一种简单却又非常高效的求最大公约数的算法。

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

该算法的原理是，设a、b为两个正整数，a>b，令r=a%b，将a替换为b，b替换为r，再计算a%b，直到r=0，则最大公约数为b。

更相减损术

更相减损术是另一种求最大公约数的算法，其原理是，设a、b为两个正整数，a>b，则a-b得到的差值可能是a的约数，也可能是b的约数。如果它是a、b的公约数，那么直接返回这个差值即可；否则，将a、b的较小者替换为a-b，较大者替换为它们的差，继续重复操作直到a或b为0。

int gcd(int a, int b) {
    while (a != b) {
        if (a > b)
            a = a - b;
        else
            b = b - a;
    }
    return a;
}

质因数分解法

质因数分解法是另一种求最大公约数的方法。首先，将两个数分别分解成质因数的乘积；然后，找出它们的所有公共质因数，将这些质因数相乘即为它们的最大公约数。

int gcd(int a, int b) {
    int r = 1;
    for (int i = 2; i <= min(a, b); i++) {
        if (a % i == 0 && b % i == 0) {
            r *= i;
            a /= i;
            b /= i;
            i = 1;
        }
    }
    return r;
}

三、各种方法的比较

由于欧几里得算法的效率最高，因此一般采用该算法来求解最大公约数，而其他方法则很少使用。例如，对于1000与1001这两个数，欧几里得算法只需要7次计算就可以求出它们的最大公约数，而质因数分解法需要对它们进行质因数分解，然后再进行比较，因此需要更多的计算次数。

四、总结

本文介绍了三种求最大公约数的算法，它们分别是欧几里得算法、更相减损术和质因数分解法。其中，欧几里得算法效率最高，因此一般采用该算法来求解最大公约数。

代码示例

#include <iostream>
using namespace std;

// 求最大公约数 - 欧几里得算法
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int main() {
    int a, b;
    cout << "请输入两个正整数：" <> a >> b;
    cout << a << "和" << b << "的最大公约数是：" << gcd(a, b) << endl;
    return 0;
}

原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/199517.html