【Wikipedia】https://en.wikipedia.org/wiki/Euclidean_algorithm
- 【範例】gcd(a, b) = gcd(45, 27)
- 45 % 27 = 18, 27 % 45 = 27
- 18 % 27 = 18, 27 % 18 = 9
- 18 % 9 = 0, 9 % 18 = 9
- gcd(45, 27) = 0 + 9 = 9
【方法1】比 方法2 快很多
int gcd(int a, int b) {
while ((a %= b) && (b %= a));
return a + b;
}
【方法2】
int gcd(int m, int n) {
while (m != n) {
if (m > n) m = m - n;
else n = n - m;
}
return m;
}