最大公因數 = 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 則留言
這樣也可以:
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);
}
不錯!當 a % b == 0 時,代表 b 整除 a,所以 b 就是最大公因數。