最大公约数和最小公倍数

作者：

disheng , 2022-04-01 10:56:40 , 所有人可见 , 阅读 389

2

2

最大公约数

约数，又称因数。整数a除以整数b(b≠0)除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。

比如：4 的正约数有：1、2、4。
4除以2没有余数<–>4能被2整除<–>2能整除4–>4为2的倍数，2为4的约数(因数)

如果数a能被数b整除，a就叫做b的倍数，b就叫做a的约数。约数和倍数都表示一个整数与另一个整数的关系，不能单独存在。如只能说16是某数的倍数，2是某数的约数，而不能孤立地说16是倍数，2是约数。

几个整数中公有的约数，叫做这几个数的公约数；其中最大的一个，叫做这几个数的最大公约数。
例如：12、16的公约数有1、2、4，其中最大的一个是4，4是12与16的最大公约数，一般记为（12，16）=4。12、15、18的最大公约数是3，记为（12，15，18）=3。

定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

gcd(a,b) = gcd(b,a mod b)

int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a ; // 如果b为0就返回a(任何数除以0都得0,a和0的最大公约数是a本身)，否则返回gcd(b,a%b)这个时候就已经保证了第一个参数大于等于第二个参数
}

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为[a，b]，同样的，a，b，c的最小公倍数记为[a，b，c]，多个整数的最小公倍数也有同样的记号。

与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（a，b）。关于最小公倍数与最大公约数，我们有这样的定理：(a,b)x[a,b]=a*b(a,b均为整数)。

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

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