a024. 最大公因數(GCD)

題目連結

https://zerojudge.tw/ShowProblem?problemid=a024

解題思路

求兩數最大公因數的辦法有很多種，可以將兩數個別的因數都先求出來，再取它們的交集得到最大公因數；也可以直接求兩數公因數的最大值。但本題測資的值較大，上述方法在ZeroJudge上執行時很可能會超時(TLE)。因此，建議使用輾轉相除法，快速計算最大公因數。

輾轉相除法的概念是，兩數的最大公因數等於其中較小的數和兩數相除後的餘數的最大公因數。具體的做法是先將兩數中較大的數字除以較小的數字，基於除法運算後餘比商小的特性，可知剩下的餘一定會比原先較小的數字還小。這時原先較小的數字就成了新的運算中較大的數字，而餘則成了新的運算中較小的數字。重複運算至其中一數變成零為止，剩下的另一個數就是兩數的最大公因數。如果在看完上述文字解說後仍然無法立刻理解，可以參考維基百科上的動畫，或是昌爸工作坊提供的運算欄位列出的算式，搭配實際運算或程式演示幫助理解。

注意事項

本程式碼第7、8行使用了「條件運算子」，寫法是「(條件) ？ (敘述1) ： (敘述2)」。條件運算子在程式執行時，會依據條件決定接下來的動作。如果符合條件就回傳敘述1的值，否則回傳敘述2的值。

程式碼：C語言

#include <stdio.h>
int main() {
    //宣告變數a、b，代表輸入的兩個整數
    int a, b;
    scanf("%d%d", &a, &b);
    //宣告變數big、small，分別代表兩數中較大和較小的數字
    int big = (a > b) ? a : b;
    int small = (a > b) ? b : a;
    //輾轉相除法：將兩數中較大的數字除以較小的數字，
    //原來較小的數字作為新的運算中教大的數字，餘作為新的運算中較小的數字
    //直到其一為0時運算結束，剩下的數字就是兩數的最大公因數
    while(small != 0) {
        int temp = big;
        big = small;
        small = temp%small;
    }
    printf("%d", big);
    return 0;
}