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

Author Avatar
Patrick 2月 15, 2017

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

最小公倍数

公式:

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

最大公约数

  • 辗转相除法:用大的数除以小的数,如果有余数,就用小的数除以余数,一直到没有余数,这时候当前的除数也就是上一轮的余数为最大公约数
1
2
3
4
5
6
7
8
if (x < y)
swap(x, y);
while (x % y)
{
c = x % y;
x = y;
y = c;
}

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

  • 相减法:用大的数减小的数,如果相减后的结果不和小的数相同,则继续相减,得到相同的结果就是余数
1
2
3
4
5
6
7
8
if (x < y)
swap(x, y);
while (x - y != y)
{
c = x - y;
x = y;
y = c;
}

最大公约数就是y