一、2个数的最大公约数
int gcd(int a, int b)
{
if (b == 0) return a;
return gcd(b, a % b);
}
二、2个数的最小公倍数
int lcm(int a, int b)
{
int t = gcd(a, b);
return a / t * b;
}
证明:
假设 x = gcd(a, b),y = lcm(a, b)。
此时有 a = m * x,b = n * x,其中m,n互为质数(如果m、n不是互为质数,那仍可以从m、n中提取出一个相等的因子,那此时的x就不是最大公约数了)。
则y = m * n * x (因为a = m * x,b = n * x,而m、n互为质数{且此时m、n也是互为质数的所有值中最小的,因为x为最大公约数})。
将上式两边同时乘x,则 x * y = m * x * n * x。
可证明 lcm * gcd = a * b。
三、N个数的最大公约数
int ngcd(int *a, int n)
{
if (n == 1) return *a;
return gcd(a[n - 1], ngcd(a, n - 1))
}
每两个数所求的x = gcd(a, b),x <= a,x <= b。
四、N个数的最小公倍数
int nlcm(int *a, int n)
{
if (n == 1) return *a;
return lcm(a[n - 1], nlcm(a, n - 1));
}
每两个数所求的y = lcm(a, b),y >= a,y >= b
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)