算法｜最大公因数和最小公倍数多个详细版-JavaScript

发表于 分类于 阅读次数： 本文字数： 962 阅读时长 ≈ 3 分钟

使用 Javascript 描述了多种求两个数或多个数的 GCD 和 LCM 的方法。

最大公约数（Greatest Common Divisor）

定义
也叫最大公因数。简单：因数最大严谨：指一个或多个数中，a1 ～ an ，都能被 k 整除，k 是公约数，k 最大时即为最大公约数。

两个数的最大公约数

倒数遍历求解

找到两个数中较小的那个数，称之为a，从a开始遍历到1，找到一个都能被a和b整数的数，符合定义。

1
2
3
4
5
6
7
8
9
10
11
12
function gcd(a, b) {
  a = a && parseInt(a)
  b = b && parseInt(b)
  if (a - b > 0) {
    [a, b] = [b, a]
  }
  for(let i = a; i > 0; i--) {
    if ( a % i === 0 && b % i === 0) {
      return i
    }
  }
}

其中，当两数相差较大时，让a成为较小值是非常必要的。

辗转相除法（欧几里德算法）

前提：gcd(a, b) === gcd(b, a mod b) (a > b && a mod b > 0)
证明：
a可以表示成a = kb + r (a，b，k，r皆为正整数，且 r > 0)
假设d是a,b的一个公约数，即a和b都可以被d整除。而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知r/d为整数，因此d也是r的因数。
d是a和b的公因数，也是b和r的公因数，即d也是b,a mod b的公约数。因(a,b)和(b,a mod b)的公约数相等，则其最大公约数也相等，得证。

1
2
3
4
5
6
7
8
9
10
11
12
function gcd(a,b) {
	a = a && parseInt(a)
	b = b && parseInt(b)
	if (a < b) {
		[a, b] = [b, a]
	}
	if (a % b === 0) {
		return b
	}else {
		return gcd(b, a % b)
	}
}

简洁版：

1
2
3
function gcd(a,b) {
	return a % b ? gcd(b, a % b) : b
}

更损相减法

第一步：若都为偶数，重复除2直到最少又一个奇数，但要记下除了多少。第二步：重复用大数减小数，直到减数等于差。最大公约数为 第一步被除了多少 * 第二步的差。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function gcd(a,b) {
	a = a && parseInt(a)
	b = b && parseInt(b)
	// 若两个相等，不作判断后面死循环
	if (a === b) {
		return a
	}
	if (a < b) {
		[a, b] = [b, a]
	}
	// 除2
	let sum = 1
	while (a % 2 === 0 && b % 2 === 0) {
		a /= 2
		b /= 2
		sum *= 2
	}
	// 开始相减
	let poor = a - b
	while (poor !== b) {
		if (poor < b) {
			a = b
			b = poor
		}else {
			a = poor
		}
		poor = a - b
	}
	return poor * sum
}

多个数的最大公约数

若参数个数为0，返回 undefined ，若参数个数为1，返回该参数。否则先求解前2个参数的最大公约数，然后用该最大公约数和第三个数求最大公约数，以此类推。

1
2
3
4
5
6
function gcdMoreNumber() {
	let arr = Array.from(arguments)
	if (arr.length < 1) return 
	while (arr.length > 1) arr.splice(0,2,gcd(arr[0], arr[1]))
	return arr[0]
}

最小公倍数（Least Common Multiple）

定义
简单：倍数最小严谨：指一个或多个数中，a1 ～ an ，k 都是他们任何一个的倍数，k 是公倍数，k 最小时即为最小公倍数。

两个数的最小公倍数

乘积 = 最小公倍数 * 最大公因数所以 最小公倍数 = 乘积 / 最大公因数

1
2
3
function lcm(a,b) {
	return (a * b) / gcd(a,b)
}

多个数的最小公倍数

原理跟多个数的最大公因数相同。

1
2
3
4
5
6
function lcmMoreNumber() {
	let arr = Array.from(arguments)
	if (arr.length < 1) return 
	while (arr.length > 1) arr.splice(0,2,lcm(arr[0], arr[1]))
	return arr[0]
}

参考：

  1. 【js计算多个数的最大公约数和最小公倍数】：https://www.cnblogs.com/Ingots/p/11330355.html
  2. 【前端JS算法之最大公因数】：https://blog.csdn.net/weixin_44388087/article/details/110388252
  3. 【百度百科：更相减损术】：https://baike.baidu.com/item/%E6%9B%B4%E7%9B%B8%E5%87%8F%E6%8D%9F%E6%9C%AF/449183
  4. 【百度百科：欧几里得算法】：https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95/1647675
  5. 【百度百科：最小公倍数】：https://baike.baidu.com/item/%E6%9C%80%E5%B0%8F%E5%85%AC%E5%80%8D%E6%95%B0/6192375

首发地址：https://WU-Kave.github.io/2022/gcd-lcm-one-and-more-js.html