今天用到了，又忘了，复习下。
1 def gcd(a,b):
2 '''Greatest Common Divisor最大公约数：辗转相除法递归'''
3 if a < b:
4 a, b = b, a
5 if b != 0:
6 return gcd(b,a%b)
7 else:
8 return a
9
10 def gcd2(a,b):
11 '''辗转相除法非递归'''
12 if a < b:
13 a, b = b, a
14 while b != 0:
15 c = a % b
16 a = b
17 b = c
18 return a
19
20 def gcd3(a,b):
21 '''这个应该就是最原始的思想了：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数'''
22 while a != 0:
23 if a >= b:
24 a -= b
25 else:
26 a, b = b, a
27 return b
28
29 def lcm(a,b):
30 '''Least Common Multiple 最小公倍数 = a * b / 最大公约数'''
31 return a * b / gcd(a,b)