【算法】求最大公因子（輾轉相除法）

1. 題目

求最大公因子（輾轉相除法）。

求任意兩個整數M,N最大公因子(M,N)的方法如下：

若　M=N*Q+R，其中: R為餘數,　滿足 O≤R≤N-1 ，

則　(M,N)=(N,R) 且當　R=0時， (M,N)=N。

例如，（1500，550）的求解過程如下：

（1500，550）=（550，400）
=（400，150）=（150，100）
=（100，50）=（50，0）=50
      

2. 實作思路

使用循環判斷第二個整數是否為0即可。

3. C實作

/* 碾轉相除法求最大公因子 */
int hcf(int m, int n)
{
    int t;
    while(n != 0)
    {
        t= m % n;
        m = n;
        n = t;
    }

    return m;
}
      

#include <stdio.h>

/* 碾轉相除法求最大公因子 */
int hcf(int m, int n)
{
    int t;
    while(n != 0)
    {
        t= m % n;
        m = n;
        n = t;
    }

    return m;
}


int main()
{
    printf("%d\n", hcf(1500,550));

    return 0;
}