基础算法

欧几里得算法

算法E: 给出两个整数m和n,找出它们的最大公约数.即,能被m和n整除的最大整数

E1. [取余]记r=m%n,(0<=r<n)
E2. [是否为0]如果r=0,则最大公约数为n
E3. [递归]使m<-n, n<-r,继续E1

原理:两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。

haskell:

gcd' :: Int -> Int -> Int
gcd' m n
    | r == 0 = n
    | otherwise = gcd' n r
    where r = mod m n

python:

def gcd(m, n):
    r = m % n
    if r == 0:
        return n
    else:
        return gcd(n, r)