算法设计------计算最大公约数

发表于 | 分类于

欧几里德算法（辗转相除法）

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。
公式：gcd(a,b) = gcd(b,a mod b) (设 a > b )

两个欧几里得的重要结论

gcd(a,b) = gcd(b,a mod b)
gcd(a,0) = a

算法实现

递归实现
1
2
3
4
int gcd(int a , int b){
    if (b == 0) return a;
    else return gcd(b, a%b);
}
非递归实现
1
2
3
4
5
6
7
8
int gcd(int a , int b){
    while (b) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}
时间复杂度

递归实现与非递归实现算法的时间复杂度均为：O(㏒ a + b)

如果对你有帮助的话，Star✨下一吧！