算法

质数

质数：除了 1 和该数自身外，无法被其他自然数整除的数。

注：

  • 2 和 3 是所有素数中唯一两个连着的数
  • 2 是唯一一个为偶数的质数
  • 质数的个数是无穷的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 求规定范围内的质数
function prime(min = 1, max = 10000) {
  const result = []

  for (let i = min; i <= max; i++) {
    let flag = true
    for (let j = min + 1; j < i; j++) {
      if (i % j === 0) {
        flag = false
      }
    }
    if (flag) {
      result.push(i)
    }
  }

  return result
}

最大公约数

如果数 a 能被数 b 整除，a 就叫做 b 的倍数，b 就叫做 a 的约数。
如 15 能被 3 整除，15 是 3 的倍数，3 是 15 的约数

12、16 的公约数有 1、2、4，其中最大的一个是 4，4 是 12 与 16 的最大公约数，一般记为 (12, 16) = 4

辗转相除法（欧几里得算法）: gcd(a, b) = gcd(b, a mod b)

1
2
3
4
5
6
7
8
9
10
11
12
13
// 欧几里得算法 求两个数的最大公约数
function gcd(a, b) {
  if (a < b) {
    ;[a, b] = [b, a]
  }

  return a % b === 0 ? b : gcd(b, a % b)
}

// 求多个数的最大公约数
function gcds(nums) {
  return nums.reduce((a, b) => gcd(a, b))
}

最小公倍数

4 和 6 的公倍数有 12、24，……，其中最小的是 12，一般记为 [4, 6] = 12

最大公约数 和 最小公倍数 的关系：(a, b) * [a, b] = a * b

1
2
3
4
5
6
7
8
9
// 公式法 求两个数的最小公倍数
function lcm(a, b) {
  return (a * b) / gcd(a, b)
}

// 求多个数的最小公倍数
function lcms(nums) {
  return nums.reduce((a, b) => lcm(a, b))
}
0%