C++7行代码实现求最大公约数

最近在做奥赛题时碰到求最大公约数的问题，给出解决方案：

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

使用递归的方法能有效缩短代码长度，达到目的。

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。算法是用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。贴张图：

C++7行代码实现求最大公约数

原文链接: https://www.cnblogs.com/SirJackie/p/11363135.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/301067

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

C++7行代码实现求最大公约数

相关推荐