Question

最大公约数与最小公倍数：辗转相除法

Answer 1

已知两个数x和y，求x和y的最大公约数

暴力循环求解：

辗转相除法求解：

辗转相除法递归求解：

理解辗转相除法：

最小公倍数：

【定理】：两个数的乘积等于这两个数的最大公约数与最小公倍数的积，即（a，b）×[a，b]=a×b，a，b的最大公约数记为（a，b），a，b的最小公倍数记为[a，b]。

所以 [a，b]=a×b / (a，b)

两个数的最小公倍数求解：

求多个数的最大公约数和最小公倍数：

讲解：