python笔记

辗转相除法找最大公约数的python实现

辗转相除法,参加维基百科:http://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95

最大公约数的python最常见算法:

1
2
3
4
5
6
7
def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a

最小公倍数就是 两个数的乘积除以最大公约数.

1
2
def ICM(a, b):
    return a * b / GCD(a, b)