求最大公因数的两种方法(高效方法)
给定两个数,例如a=27,b=12a=27, b=12a=27,b=12,我们知道a, b的最大公因数为3。下面将介绍两种求最大公因数的高效方法:(1)辗转相除法辗转相除法有一个高大上的名字:欧几里得法。下面模拟辗转相除法求a, b的最大公因数:Created with Raphaël 2.2.0开始a = 27, b = 12c = a%ba = b, b=cb=0?输出最大公因数...
文章共4,464字 · 阅读需要大约15分钟
一键AI生成摘要,助你高效阅读
问答
·
给定两个数,例如
a
=
27
,
b
=
12
a=27, b=12
a=27,b=12,我们知道a, b
的最大公因数为3
。
下面将介绍两种求最大公因数的高效方法:
(1)辗转相除法
辗转相除法有一个高大上的名字:欧几里得法。
下面模拟辗转相除法求a, b
的最大公因数:
辗转相除法的代码如下:这里采用递归,并且是精简形式。
int gcd_1(int a, int b){
return b == 0 ? a:gcd_1(b, a%b);
}
(2)辗转相减法
辗转相减法也有一个高大上的名字:尼考曼彻斯法。
下面模拟辗转相减法求a, b
的最大公因数:
辗转相减法的代码如下:这里也采用递归,并且也是精简形式。
int gcd_2(int a, int b){
return a == b ? a:gcd_2(a>b ? a-b:a, b>a ? b-a:b);
}
更多推荐
已为社区贡献1条内容
所有评论(0)