# andyRon/swift-algorithm-club-cn

Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
GCD.playground

# 最大公约数算法（Greatest Common Divisor）

``````gcd(a, b) = gcd(b, a % b)
``````

```func gcd(_ a: Int, _ b: Int) -> Int {
let r = a % b
if r != 0 {
return gcd(b, r)
} else {
return b
}
}```

```gcd(52, 39)        // 13
gcd(228, 36)       // 12
gcd(51357, 3819)   // 57```

``````gcd(51357, 3819)
``````

``````gcd(3819, 51357 % 3819) = gcd(3819, 1710)
``````

``````gcd(3819, 1710) = gcd(1710, 3819 % 1710) =
gcd(1710, 399)  = gcd(399, 1710 % 399)   =
gcd(399, 114)   = gcd(114, 399 % 114)    =
gcd(114, 57)    = gcd(57, 114 % 57)      =
gcd(57, 0)
``````

``````gcd(3819, 51357) = gcd(57, 0) = 57
``````

`gcd(841, 299)     // 1`

```func gcd(_ m: Int, _ n: Int) -> Int {
var a = 0
var b = max(m, n)
var r = min(m, n)

while r != 0 {
a = b
b = r
r = a % b
}
return b
}```

## 最小公倍数

``````              a * b
lcm(a, b) = ---------
gcd(a, b)
``````

```func lcm(_ m: Int, _ n: Int) -> Int {
return m / gcd(m, n) * n
}```

`lcm(10, 8)    // 40`

You can’t perform that action at this time.