如何求最小公约数和最大公倍数
2021 年 09 月 10 日 84 297 字 暂无评论

记录:假设x和y的最大公约数是m,最小公倍数是n,则xy=mn

1、公约数

公约数,亦称“公因数”。它是一个能被若干个整数同时均整除的 整数。如果一个整数同时是几个整数的 约数,称这个整数为它们的“公约数”;公约数中最大的称为最大公约数。

求两个数最大公约数的方法

  • 倍数关系

    • 若较大数是较小数的 倍数,那么较小数就是这两个数的最大公约数。
  • 互质关系

    • 若这两个数是 互质数,那么它们的最大公约数就是1.

代码实现

int gcd(int a, int b){
    return (b ? gcd(b, a%b) : a);
}

2、公倍数

公倍数(common multiple)指在两个或两个以上的自然数中,如果它们有相同的倍数,这些倍数就是它们的公倍数。

公倍数举例

A和B A/B=C 如果A能被B整除,则A为B和C的公倍数 两个数A和B,它们的公倍数就是既是A的倍数又是B的倍数的数,即能同时被A、B整除的数  比如说:12和15,它们的公倍数是60,120,180,等等 在这些公倍数中最小的那一个就叫最小公倍数,就是60。

代码实现

int lcm(int a, int b){
    return a / gcd(a, b) * b;
}

版权属于:zfh

本文链接:http://zfhblog.com/index.php/archives/231/



评论已关闭