求最大公因数的两种数学方法

本文主要是介绍求最大公因数的两种数学方法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1. 更相减损术

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
——《九章算术》

int gcd(int a, int b) {
    if (a > b)
        return gcd(a-b, b);
    if (a < b)
        return gcd(b-a, a);
    return a;
}

2. 辗转相除法

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

这篇关于求最大公因数的两种数学方法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！