# ユークリッドの互除法
[ユークリッドの互除法 - Wikipedia](https://ja.wikipedia.org/wiki/ユークリッドの互除法)
最大公約数 (GCD: Greatest Common Divisor) を効率よく計算する方法。
```
GCD(300, 780)
780 / 300 = 2 ... 180
300 / 180 = 1 ... 120
180 / 120 = 1 ... 60
120 / 60 = 2
GCD(300, 780) = 60
```
Go による実装。
```go
package main
func GCD(a, b int) int {
if b == 0 {
return a
}
return GCD(b, a%b)
}
func main() {
println(GCD(300, 780))
}
```
計算量は $O(\log{a})$ 。
（ざっくり半、半、... になっていく）