用辗转相除法求最大公约数
萌到你眼炸
873次浏览
2021年02月13日 16:32
最佳经验
本文由作者推荐
-
个人收集整理
-ZQ
百科名片
辗除法（
ǎú ǎ
）
——
辗转相除法，
又名欧几里德算法（
）乃求两个正整
数之最大公因子地
算法
.
它是已知最古
老地算法，
其可追溯至年前
.
它首次出现于欧几里德地《几何原本》
（第
卷
，命题和）中，而在中国则可以追溯至东汉出现地《九章算术》
.
它并不需要把二数作质
因子分解
.
资
料个人收集整理，勿做商业用途
证明：
设两数为、
(<)
，求它们最大公约数
(
、
)
地步骤
如下：用除，得
(≤).
若，则
(
，
)
；若
≠
，则
再用除，得
(≤).
若，则
(
，
)
，若
≠
，则继续用除
,……
如此下去，直到能整除为止
.
其最后一个非
零余数即为
(
，
).
资料个人收集整理，勿做商业
用途
[
编辑
]
算法
辗转相除法是利用以下性质来确定两个正整数
.
若
是
÷
地余数
,
则
()
()
.
和其倍数之最大公因子为
.
另一种写法是：
.
÷
，令为所得余数（
≤<
）
若
，算法结束；
即为答案
.
.
互换：置
←
，
←
，并返回第一步
.
[
编辑
]
虚拟码
这个算法可以用递归写成如下
:
(,
) {
<>
(,
);
;
}
或纯使用循环
:
(,
) {
;
≠
{
;
;
;
}
;
}
代码（递归）
求两数地最大公约数
();
(
);
;
其中
“
”
是指取
÷
地余数
.
1
/ 3
和
地最大公因子地：