【筆記】Euclidean algorithm 輾轉相除法

【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;
}
分享本文 Share with friends