求公约数的计算公式

Question

如题所述

Answer 1

求公约数的计算方法是：辗转相除法.

辗转相除法：

辗转相除法又名欧几里德算法(Euclidean algorithm)，是求两个正整数之最大公约数的算法。它是已知最古老的算法，其可追溯至公元前300年前。

它的具体做法是：权界用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。 

另一种求两数的最大公约数的方法是更相减损法。

使用：

设两数为a、b来自(a>b)，求a与b最大公约数360百科(a，b)注：（）为最大公约数的符号的步骤如下:用a除以b，r1为余数：除够本础财推也营即a÷b=q.....r1(0≤r1)。若r1=0，则(a，b)=b;若r1≠0，则再用b除以r1，r2为余数。

即b÷r1=q.......r2 (0≤r2）若r2=0，则(a，b)=r1，若r2≠0，则继续用r1除以r2，如此下去，直到能整除为止。其最后一个为被除数的余数的除数即为(a, b)。

辗转相除法的算法步骤：

两个数中用较大数除以较小数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。得到最后的除数就是这两个数的最大公约数。