【C++】輾轉相除法求最大公因數

最大公因數 = Greatest Common Divisor = GCD

#include <iostream>
using namespace std;

int main(){
    int a, b, temp;
    cin >> a >> b;
    while (b != 0) { // (a, b) = (b, a % b)
        temp = b;
        b = a % b;
        a = temp;
    }
    cout << a << '\n';
}

寫法二:當 a % b == 0 時,代表 b 整除 a,所以 b 就是最大公因數。

int gcd(int a, int b) {
   if (a % b == 0) return b;
   return gcd(b, a % b);
}

2 則留言
  1. 這樣也可以:
    int gcd(int a, int b){
    if(a % b == 0) return b;
    return gcd(b, a % b);
    }

    int main(){
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b);
    }

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *