網頁

2015年3月18日 星期三

為什麼使用輾轉相除法來求2整數之最大公因數,不必考慮2數大小的順序?

輾轉相除法求2數最大公因數的函式

int gcd(int a, int b)
{
int temp = 1;
while (temp != 0)
{
temp = a % b;
a = b;
b = temp;
}
return a;
}

假設有2703 407
先看看,如果輸入大小順序為 703, 407  (a > b)