您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 使用技巧 >> iOS 技巧大全

最大公約數與最小公倍數的求解

編輯:iOS 技巧大全
[摘要]本文以 C 語言實作求兩正整數最大公約數與最小公倍數的程式,對學習 iOS 開發有所幫助,與大家分享。

問題描述:給出兩個正整數,求它們的最大公約數與最小公倍數。

輸入:第一行輸入整數 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;
}

這裡最大公約數採用輾轉相除法(歐幾里得演算法)的遞迴實作,最小公倍數則利用「兩數之積除以最大公約數」的關係求得。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved