两个整数a和b的公约数里最大的那一个叫做它们的最大公约数，记为[a, b]；两个整数a和b的 公倍数里最小的那一个叫做它们的最小公倍数，记为(a, b)。例如： [12, 15] = 3，(12, 15) = 60。 [20, 35] = 5，(20, 35) = 140。

  求两个整数的最大公约数和最小公倍数。

最大公约数和最小公倍数

问题描述

 两个整数a和b的公约数里最大的那一个叫做它们的最大公约数，记为[a, b]；两个整数a和b的 公倍数里最小的那一个叫做它们的最小公倍数，记为(a, b)。例如： [12, 15] = 3，(12, 15) = 60。 [20, 35] = 5，(20, 35) = 140。

  求两个整数的最大公约数和最小公倍数。

 设计思路

如果 a < b，则交换 a 和 b 的值，以确保 a >= b。 设置循环变量 maxGY，maxGY 从 b 开始递减至 1。在循环的过程中，如果 maxGY 同时为 a 和 b 的约数，那么最先出现的 maxGY 显然为 a 和 b 的最大公约数。 设置循环变量 minGB，minGB 从 a 开始递增。在循环的过程中，如果 minGB 同时为 a 和 b 的 倍数，那么最先出现的 minGB 显然为 a 和 b 的最小公倍数。

 如果 a < b，则交换 a 和 b 的值，以确保 a >= b。 “辗转相除法”的算法思想是：

（1）a 除以 b 得余数 r，若 r = 0，则 b 为所求的最大公约数；

（2）若 r ≠ 0，以 b 为 a，以 r 为 b，继续步骤（1）。

例如：求(377, 319)

377 ÷ 319 = 1（余 58）

319 ÷ 58 = 5（余 29）

58 ÷ 29 = 2（余 0）

所以，(377, 319) = 29

 求出最大公约数之后，可以根据如下定理求最小公倍数：(a, b) * [a, b] = a * b。

Swift 3.0 代码实现

求两个整数的最大公约数和最小公倍数（思路一：根据最大公约数和最小公倍数的定义）

func calMaxGYAndMinGB1(a : Int, b : Int) -> (maxGY : Int, minGB: Int) {
    var a = a
    var b = b
    
    if a < b {
        (a, b) = (b, a)
    }
    
    var maxGY = b
    while maxGY > 1 {
        if a % maxGY == 0 && b % maxGY == 0 {
            break
        }
        maxGY -= 1
    }
    
    var  minGB = a
    while true {
        if minGB % a == 0 && minGB % b == 0 {
            break
        }
        minGB += 1
    }
    
    return (maxGY, minGB)
}

calMaxGYAndMinGB1(a: 12, b: 15)
calMaxGYAndMinGB1(a: 20, b: 35)

求两个整数的最大公约数和最小公倍数（思路二：根据“辗转相除法”（“欧几里得算法”））

func calMaxGYAndMinGB2(a : Int, b : Int) -> (maxGY : Int, minGB: Int) {
    var a = a
    var b = b
    let ab = a * b
    
    if a < b {
        (a, b) = (b, a)
    }
    
    var r = a % b
    while r != 0 {
        a = b
        b = r
        r = a % b
    }
    
    return (b, ab / b)
}

calMaxGYAndMinGB2(a: 12, b: 15)
calMaxGYAndMinGB2(a: 20, b: 35)

算法理解