怎样求两个数的最大公约数？

Question

如题所述

Answer 1

两个数的最大公约数算法有辗转相除法、相减法、穷举法。

1、辗转相除法：取两个数中最大的数做除数，较小的数做被除数，用最大的数除较小数，如果余数为0，则较小数为这两个数的最大公约数，如果余数不为0，用较小数除上一步计算出的余数，直到余数为0，则这两个数的最大公约数为上一步的余数。

2、相减法：取两个数中的最大的数做减数，较小的数做被减数，用最大的数减去小数，如果结果为0，则被减数就是这两个数的最大公约数，如果结果不为0，则继续用这两个数中最大的数减较小的数，直到结果为0，则最大公约数为被减数。

3、穷举法：将两个数作比较，取较小的数，以这个数为被除数分别和输入的两个数做除法运算，被除数每做一次除法运算，值减少1，直到两个运算的余数都为0，则该被除数为这两个数的最大公约数。

最大公约数介绍

最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。a，b的最大公约数记为（a，b），同样的，a，b，c的最大公约数记为（a，b，c），多个整数的最大公约数也有同样的记号。

Answer 2

两个数的最大公约数有很多求法：
小学用两种方法：
1. 对两个数分解质因数，相同的质因数相乘得到最大公约数
2. 短除法，找两个数都可以整除的质数，然后商重复前面的步骤，一直到商互质。那么把这些除数相乘就是最大公约数。