【方法一】辗转求余法
int gcd(int a,int b){ if(a<b)swap(a,b); if(a%b==0)return b; else gcd(b,a%b); }
【方法二】辗转相减法
int gcd(int a,int b){ if(a<b)swap(a,b); if(a%b==0)return b; else gcd(b,a-b); }
【方法三】连续整数检测法:从较小数的1/2开始从大到小测试,如果可以整除就是最大公约数。
int gcd(int a,int b){ if(a<b)swap(a,b); if(a%b==0)return b; for(int i=b/2+1;i>0;i--){ if(a%i==0&&b%i==0)return i; } }
原文链接: https://www.cnblogs.com/ziyuwang/p/10391037.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/290057
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!