怎么求公约数
最大公约数的求法一共有三种：
1、找查约数法：分别找出两个数的所有约数，再找出两个数的所有公约数，最大的那个就是最大公约数。
2、更相减损法：任意两个数，判定是否为偶数，是就用2约简，不是就用较大的数减较小的数，所得的差和较小的数比较，再用大的减小的，直到所得的减数和差相等，再用约掉的2的个数与所得的相等的数的乘积就是最大公约数。
3、辗转相除法：以小的数除大数，所得的是整数，那这个数就是最大公约数，不然就用余数来除刚才的除数，直到得到整数，这时作为除数的就是最大公约数。
如何求公约数
短除法：短除法求最大公约数，先用这几个数的公约数连续去除，一直除到所有的商互质为止，然后把所有的除数连乘起来，所得的积就是这几个数的最大公约数。短除法的本质就是质因数分解法，只是将质因数分解用短除符号来进行。短除符号就是除号倒过来。短除就是在除法中写除数的地方写两个数共有的质因数，然后落下两个数被公有质因数整除的商，之后再除，以此类推，直到结果互质为止（两个数互质）。多位数除法的法则：（1）从被除数的高位除起，除数有几位，就看被除数的前几位，如果不够除，就多看一位。（2）除到被除数的哪一位，就把商写在哪一位的上面，如果不够除，就在这一位上商0。（3）每次除得的余数必须比除数小，并在余数右边一位落下被除数在这一位上的数，再继续除。
欧几里得方法
欧几里得的方法如下：欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应gfa用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。欧几里得算法和扩展欧几里得算法可使用多种编程语言实现。欧几里得算法是用来求两个正整数最大公约数的算法。古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。扩展欧几里得算法可用于RSA加密等领域。 假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里得算法，是这样进行的：1997 ÷ 615 = 3 (余 152)615 ÷ 152 = 4(余7)152 ÷ 7 = 21(余5)7 ÷ 5 = 1 (余2)5 ÷ 2 = 2 (余1)2 ÷ 1 = 2 (余0)至此，最大公约数为1以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。 辗转相除法是利用以下性质来确定两个正整数 a 和 b 的最大公因子的：⒈ 若 r 是 a ÷ b 的余数，且r不为0， 则gcd(a,b) = gcd(b,r)⒉ a 和其倍数之最大公因子为 a。另一种写法是：⒈ 令r为a/b所得余数（0≤r若 r= 0，算法结束；b 即为答案。⒉ 互换：置 a←b，b←r，并返回第一步。