求最大公约数和最小公倍数 | Patrick's Space

求最大公约数和最小公倍数

最小公倍数

公式：

最小公倍数 = x * y / x与y的最大公约数

最大公约数

• 辗转相除法：用大的数除以小的数，如果有余数，就用小的数除以余数，一直到没有余数，这时候当前的除数也就是上一轮的余数为最大公约数

if (x < y)
    swap(x, y);
while (x % y)
{
    c = x % y;
    x = y;
    y = c;
}

最大公约数就是y， 也就是除尽之前的余数

• 相减法：用大的数减小的数，如果相减后的结果不和小的数相同，则继续相减，得到相同的结果就是余数

if (x < y)
    swap(x, y);
while (x - y != y)
{
    c = x - y;
    x = y;
    y = c;
}

最大公约数就是y