#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 為止。
阿摩線上測驗
登入