Question

如何找最大公因数，有哪些公式？

Answer 1

辗转相除法

利用辗转相除法求最大公约数的算法步骤如下：
第一步：给定两个正整数m，n.
第二步：用较大的数m除以较小的数n所得余数r.
第三步：m=n,n=r.
第四步：若r=0，则m,n的最大公约数等于m;否则,返回到第二步.
……
依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数.

更相减损术

<九章算术>是中国古代的数学专著,其中的“更相减损术”也可以用来求最大公约数，
其步骤如下：可半者半之，不可半者，副置分母，子之数，以少减多，更相减损，求其等也，以等数约之.
即为：第一步：任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数.