問題描述:給出兩個正整數,求它們的最大公約數與最小公倍數。
輸入:第一行輸入整數 n(0<n≤10000),表示有 n 組測試資料;隨後的 n 行各輸入兩個整數 i、j(0<i,j≤32767)。
輸出:輸出每組測試資料的最大公約數與最小公倍數。
樣例輸入:
3 6 6 12 11 33 22
樣例輸出:
6 6 1 132 11 66
程式碼:
#include <stdio.h>
// 最大公約數(輾轉相除法)
int gcd(int a, int b) {
if (a < b) return gcd(b, a);
else if (b == 0) return a;
else return gcd(b, a % b);
}
// 最小公倍數
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int main(int argc, const char * argv[]) {
printf("Hello, World!\n");
int a, b, n;
scanf("%d", &n);
while (n > 0) {
scanf("%d%d", &a, &b);
printf("最大公約數:%d\n", gcd(a, b));
printf("最小公倍數:%d\n", lcm(a, b));
n--;
}
return 0;
}
這裡最大公約數採用輾轉相除法(歐幾里得演算法)的遞迴實作,最小公倍數則利用「兩數之積除以最大公約數」的關係求得。