a024: 最大公因數(GCD)

2019-08-11

內容

給定兩個數字，請得出它們的最大公因數

輸入

兩個整數大於 0, 小於 2³¹

12 15

輸出

最大公因數為一整數

3

解題思路

利用輾轉相除法的原理，不斷的取較大數除以較小數的餘數，直到較小數變成 0 為止，較大數即為最公因式。

完整程式碼

AC (2ms, 92KB)

#include <stdio.h>
#define SWAP(x, y) \
    x = x ^ y,     \
    y = x ^ y,     \
    x = x ^ y

int m, n;

int main()
{
    while (scanf(" %d %d", &m , &n) == 2)
    {
        while (n)
        {
            m %= n;
            SWAP(m, n);
        }
        printf("%d\n", m);
    }
    return 0;
}