求a和b的最大公约数：
1
2
|
Input : 319, 377
Output: 29
|
解法
采用欧几里德算法（又称辗转相除法），定理：gcd(a,b) = gcd(b,a mod b)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
// 求最大公约数 Greatest Common Divisor
// 辗转相除法(欧几里德算法)
func gcd(a, b int) int {
if a < b {
return gcd(b, a)
}
for {
remain := a % b
if remain == 0 {
return b
}
a = b
b = remain
}
}
|
评论