最大公约数
质数和合数
- 质数也称素数， 指大于1， 并且除了1和它自己， 不能被任何其他自然数整除的数。
- 除了1和质数的其他自然数称为合数， 合数必定可以分解成2个或以上个质数相乘。例如4 = 2 x 2, 6 = 2 x 3。
公约数
一个自然数a的约数表示能整除a的数，把一个数作因式分解，变成若干质数的乘积，例如 24 = 2 x 3 x 4, 所有质因数的乘法组合，都是它的约数。例如2，3，4， 2x3, 2x4, 3x4, 2x3x4都是24的约数， 公约数是指两个数a, b相同的约数， 其中最大的那个就是公约数。例如30 = 2 x 3 x 5, 与24的公约数有2， 3， 2 x 3, 最大公约数便是6。
计算最大公约数
求a和b的最大公约数，假设a > b， a % b == c，
- 如果c == 0, 则b能整除a, b同时也能整除它自己, a, b的最大公约数便是b。
- 如果c != 0, c就是a在取模b后的余数部分， 正是多了无法被b整除的这部分， 确定b不能作为它们的公约数。假设div = a / b。 div肯定是b的倍数， 假设b和c的最大公约数为d， d能整除b, 能整除c。 则d必定能整除作为b的倍数的div, d必定能整除a == (div + c), 也为a的约数。
- 虽然d是(b, c)的最大公约数， 并且是a的约数， 为何为何d是(a, b, c)最大的公约数？ 不能存在
d_bigger > d, 是(a, b, c)的最大公约数吗？ 答案是不能， 假如d_bigger存在，它是(a, b, c)的最大公约数，它必然是(b, c)的约数(不一定是最大)， 由于d_bigger > d, 显然与d 是(a, b)的最大公约数矛盾， 如果d_bigger存在， 那么d就不可能是(b, c)的最大公约数。
辗转相除法
求(a, b)的最大公约数， a > b, c = a % b, 如果c == 0, 则结果为b, 如果c != 0, 问题转化为求b, c的最大公约数。 通过循环或者递归即可解决此问题。
代码实现
// 循环
long long GreatestCommonDivisor(long long a, long long b)
{
if (a == 0 || b == 0) {
return 0;
}
long long max, min;
if (a < b) {
min = a;
max = b;
}
else {
min = b;
max = a;
}
long long the_mod = max % min;
while (the_mod != 0){
max = min;
min = the_mod;
the_mod = max % min;
}
return min;
}
// 递归
long long GreatestCommonDivisor(long long a, long long b)
{
if (a == 0 || b == 0) {
return 0;
}
long long max, min;
if (a < b) {
min = a;
max = b;
}
else {
min = b;
max = a;
}
long long the_mod = max % min;
if(the_mod == 0){
return min;
}else{
return GreatestCommonDivisor(min, the_mod);
}
}
最小公倍数
一个自然数a的倍数， 必然是包含它所有质因数的数， a, b的公倍数， 就是既包含a的所有质因子，也包含b的所有质因子的数。 最公倍数就是, 满足包含a, b所有质因子的条件下， 质因子能少就少。 假设a = 24 = 2 x 3 x 4, 则24的所有质因数2, 3, 4都必不可少， b = 30 = 2 x 3 x 5, 它的所有质因数2, 3, 5都是必不可少， a和b存在重复的部分， 这些重复的部分， 可以只要1份就好， 最终得到的一定是a, b的倍数， 并且是最少了。 而a, b，的质因数公共部分的乘积， 恰恰就是最大公约数。 假如最大公约数为c, a除去最大公约数后剩下的部分就是a / c, b除去最大公约数后剩下的部分是b / c, 最大公约数只要一份就好。因此最小公倍数的公式
lcm = c * (a / c) * (b / c) = a * b / c。
代码实现
long long LeastCommonMultiple(long long a, long long b)
{
if (a == 0 || b == 0) {
return 0;
}
return a * b / GreatestCommonDivisor(a, b);
}
