欧几里得算法(辗转相除法)
递归实现
1
2
3
4
5
| private int gcd(int x, int y){
if(y == 0) return x;
return gcd(y, x % y);
}
|
迭代实现
1
2
3
4
5
6
7
8
| public int gcd(int x, int y) {
while(y != 0) {
int tmp = x;
x = y;
y = tmp % y;
}
return a;
}
|
例题
[easy]1071. Greatest Common Divisor of Strings
如有遗漏或错误,欢迎补充纠正