求最大公约数和最小公倍数

发表于 | 阅读次数:

辗转相除法的推导：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
求x和y的最大公约数:
假设 k = x / y , b = x % y, 则：
1. x = k * y + b;
假设 g为x和y的最大公约数: 则：
2. x = g * c1 ; 
3. y = g * c2 ; (c1, c2为某个常数)

将1带入2，可得：
4. k * y + b = g * c1;
将3带入4，可得：
k * (g * c2) + b = g * c1 ==> b = g * (c1 - k*c2)
从而可得: b = g * c3;

于是求x和y最大公约数函数 f(x, y) = f(y, b),
'''
def gcd(x, y):
    return x if y==0 else gcd(y, x%y)

辗转相减法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
求x和y的最大公约数:
假设 g为x和y的最大公约数: 则：
1. x = g * c1 ; 
2. y = g * c2 ; (c1, c2为某个常数)
1减去2可得：
x-y = g * (c1-c2)
则可以推导出 y和x-y的最大公约数也是g ：
于是：f(x, y) = f(y, x-y)
'''
def gcd_sub(x, y):
    while(y):
        if y > x:
            x, y = y, x
        x, y = y, x-y
    return x