題組內容

四、所謂互質為兩個或兩個以上的整數彼此之間的最大公因數是1，而最簡分數為分子和分母互質的分數。

(一)請使用C語言完成函數int coprime (int a, int b)，來檢查正整數a與b是否互質。如果互質，則函數回傳值為1，反之回傳0。（10分）

詳解 (共 1 筆)

詳解 提供者：hchungw
#include <stdio.h>
// 計算兩個數的最大公因數
int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}
// 檢查兩個數是否互質
int coprime(int a, int b) {
    if (gcd(a, b) == 1)
        return 1;  // 互質
    else
        return 0;  // 不互質
}
int main() {
    int num1, num2;
    printf("輸入兩個正整數: ");
    scanf("%d %d", &num1, &num2);
    if (coprime(num1, num2))
        printf("%d 和 %d 是互質的\n", num1, num2);
    else
        printf("%d 和 %d 不是互質的\n", num1, num2);
    return 0;
}
解釋：
首先定義一個輔助函數 gcd，用來計算兩個數的最大公因數，使用遞迴的方式實作。
定義函數 coprime，其中先使用 gcd 函數計算 a 和 b 的最大公因數，如果結果為 1，則表示 a 和 b 互質，回傳 1；否則回傳 0。
在 main 函數中，讀入兩個正整數 num1 和 num2，並呼叫 coprime 函數檢查它們是否互質，根據回傳值印出結果。
執行範例：
Copy code輸入兩個正整數: 12 35
12 和 35 是互質的
輸入兩個正整數: 8 12
8 和 12 不是互質的
這個實作方式的時間複雜度為 O(log(min(a, b)))，因為在計算最大公因數時，每次遞迴會將較小的數約減一半，直到其中一個數變為 0 為止。