算法:最大公约数(GCD)

1. 最大公约数?

因数、倍数:设 a, b 是整数,b !=0。如果有一个整数 c,它使得 a = bc,则 a 叫做 b 的倍数,b 叫做 a 的因数。我们有时说,b 能整除 a 或 a 能被 b 整除,表示为 b|a

公因数、最大公因数:如果 n >=2 是整数,而 a1, a2, ..., an 和 d 都是正整数。又设 d|a1,d|a2,d|a3,...,d|an,则 d 叫做 a1,a2,...,an 的公因数。公因数中的最大的那一个数叫做 a1,a2,a3,...,an 的最大公因数,表示为 (a1, a2, ..., an) = d

2. 辗转相除法?

辗转相除法, 又名欧几里德算法(Euclidean algorithm),是求最大公约数的一种方法。方法是:用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。那么最后的除数就是这两个数的最大公约数。

例:求 123456 和 7890 的最大公因数。

图:辗转相除过程

答: 123456 和 7890 的最大公因数是 6.

3. 数学解释?

辗转相除法的关键是

一个数学事实

GCD(a, b) = GCD(b, a mod b)

图:辗转相除数学证明

4. 程序代码?

图:辗转相除算法

原文发布于微信公众号 - WebJ2EE(WebJ2EE)

原文发表时间:2019-03-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券