gcd 函數
[編輯] [转简体] （简体译文）
|
作者：huidong
| 分類：【算法】雜項
[
6 瀏覽
0 評論
2 贊
2 踩
]
概要
求解最大公因數
正文
輾轉相除法
int gcd(int m, int n)
{
if (!m || !n)
return 1;
// 準備輾轉相除，首先使 a >= b，r 記錄餘數
int a = m, b = n, r = 0;
if (a < b)
a ^= b ^= a ^= b;
do
{
r = a % b;
a = b;
b = r;
} while (r != 0);
return a;
}m * n == 0 時返回 1。