Question

辗转相除法除到什么时候为止

Answer 1

辗转相除法除到余数为0为止。

具体而言，从定义上可知，欧几里德算法，也称辗转相除法。其基本思想是：对正整数a和b，连续进行求余运算，直到余数为0为止，此时非0的除数就是最大公约数。所以辗转相除法是一个比较重要的基础算法。

辗转相除法计算例子：

假如需要求 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。