最大公约数的四种实现方法
求最大公约数的四种方法
一：辗转相除法求最大公约数
辗转相除法：输入俩个数x和y。首先保证x>y；之后x除y得到了余数和结果。将上一个式子的除数赋值给被除数，将余数赋值给除数。判断条件为余数为0；
举个简单的例子（x：被除数，y：除数，z：结果，m：余数）
x y z m
15 12 1 3
12 3 4 0
| x | y | z | m |
|---|---|---|---|
| 15 | 12 | 1 | 3 |
| 12 | 3 | 4 | 0 |
代码实现：
二：辗转相减法求最大公约数
辗转相减法：输入两个数x和y；在保证被减数大于减数的情况下，不断循环x-y；将减数赋值给被减数，将结果赋值在减数。当x=y时（判断条件），相等的数就是最大公约数。
举个简单的例子：(x：被减数，y：减数，z：结果）
| x | y | z |
|---|---|---|
| 15 | 12 | 3 |
| 12 | 3 | 9 |
| 9 | 3 | 6 |
| 6 | 3 | 3 |
| 3 | 3 | 0 |
辗转相减法比较好理解，编写程序时也比较方便。强烈推荐。
代码：
利用三元运算符一步完成；
利用循环：
两种皆可以。
三：穷举法（也称蛮力法）
求最大公约数时，从俩个数的最小数开始，一个一个的试，直到找到最大公约数。
最原始解法，不建议使用。了解即可。
四：stein算法：
当输入的两个数均为偶数时，那么有一个公约数为2，可能更大。若输入的是一奇一偶，则最大公约数为奇数，若两个数均为奇数，则最大公约数也为奇数。