最大公约数

短除法

屏幕快照 2019-02-21 上午11.32.06.png

辗转相除法

屏幕快照 2019-02-21 上午11.34.31.png

func maxCommonDivisor(a: Int, b:Int) -> Int{
    var r = 0
    var a  = a;
    var b = b;
    if (a<b)
    {
        r=a;
        a=b;
        b=r;
    }
    while (a%b > 0) {
        r = a%b;
        a=b;
        b=r;
    }
    return b
}
print(maxCommonDivisor(a: 24, b: 60))

更相减损法

屏幕快照 2019-02-21 上午11.42.50.png

func maxCommonDivisor(a: Int, b:Int) -> Int{
    var r = 0
    var a  = a;
    var b = b;
    while (a != b) {
        if (a<b)
        {
            r=a;
            a=b;
            b=r;
        }
        r = a-b;
        a=b;
        b=r;
    }
    return b
}
print(maxCommonDivisor(a: 24, b: 60))

扩展：最小公倍数 = (a * b)/最大公约数