最大公约数求解

模型算法

在数学中，公因数显示着若干个整数之间的数论关系。如果一个数同时是几个数的约数，称这个数为它们的“公约数”；公约数中最大一个的称为最大公约数。
在数学分析的叙述中，如果n和d都是整数而且存在某个整数c，使得n = cd，就说d是n的一个因数，或说n是d的一个倍数，记作d|n（读作d整除n）。如果d|a且d|b我们就称d是a和b的一个公因数。对每一对整数都有一个公因数d，形如d = ax+by，其中x和y都是整数，并且a和b的每一个公因数都能整除这个d。d的绝对值叫做最大公因数，记为 {\displaystyle \gcd(a,b)} {\displaystyle \gcd(a,b)}。

因数分解法

质因数分解法：把每个数分别分解质因数，再把各数中的全部公有质因数提取出来连乘，所得的积就是这几个数的最大公约数。
例如：求24和60的最大公约数，先分解质因数，得24=2×2×2×3，60=2×2×3×5，24与60的全部公有的质因数是2、2、3，它们的积是2×2×3=12，所以，（24，60）=12。
把几个数先分别分解质因数，再把各数中的全部公有的质因数和独有的质因数提取出来连乘，所得的积就是这几个数的最小公倍数。

輾轉相減法

http://4rdp.blogspot.jp/2012/09/blog-post_22.html
最近小朋友剛學最大公因數 (Greatest Common Divisor)，問我兩數之間最大公因數求解，他說老師利用輾轉相減求之，其方法如下：

以較大數減較小數，較大數變小後，再繼續比較，直到兩數相等或其中某數值變成1

我畫了上圖解說，他很快理解原理。

例一：有兩數分別為 A = 7 和 B = 5，
A = 7 - 5 = 2, B = 5
A = 2, B = 5 - 2 = 3
A = 2, B = 3 - 2 = 1
最大公因數為 1

例二：有兩數分別為 A = 14 和 B = 10，
A = 14 - 10 = 4, B = 10
A = 4, B = 10 - 4 = 6
A = 4, B = 6 - 4 = 2
A = 4 - 2 = 2, B = 2
最大公因數為 2