判断质数的方法

详细内容参考 leetcode 题解

计数质数

列举三种方法

枚举法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const isPrime = (x) => {
  for (let i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      return false;
    }
  }
  return true;
};

var countPrimes = function (n) {
  let ans = 0;
  for (let i = 2; i < n; ++i) {
    ans += isPrime(i);
  }
  return ans;
};

埃氏筛

1
2
3
4
5
6
7
8
9
10
11
12
13
var countPrimes = function (n) {
  const isPrime = new Array(n).fill(1);
  let ans = 0;
  for (let i = 2; i < n; ++i) {
    if (isPrime[i]) {
      ans += 1;
      for (let j = i * i; j < n; j += i) {
        isPrime[j] = 0;
      }
    }
  }
  return ans;
};

线性筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var countPrimes = function (n) {
  const isPrime = new Array(n).fill(1);
  const primes = [];
  for (let i = 2; i < n; ++i) {
    if (isPrime[i]) {
      primes.push(i);
    }
    for (let j = 0; j < primes.length && i * primes[j] < n; ++j) {
      isPrime[i * primes[j]] = 0;
      if (i % primes[j] === 0) {
        break;
      }
    }
  }
  return primes.length;
};

最大公约数

1
2
3
4
5
6
7
8
const gcd = (num1, num2) => {
  while (num2 !== 0) {
    const temp = num1;
    num1 = num2;
    num2 = temp % num2;
  }
  return num1;
};

数组中好对子的数目

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
31
/**
 * @param {number[]} nums
 * @return {number}
 */
// 反转数字
function rev(num) {
  let temp = num,
    j = 0;
  while (temp > 0) {
    j = j * 10 + (temp % 10);
    temp = Math.floor(temp / 10);
  }
  return j;
}
var countNicePairs = function (nums) {
  const MOD = 1000000007;
  let res = 0;
  const h = new Map();
  for (const i of nums) {
    let temp = i,
      j = 0;
    while (temp > 0) {
      j = j * 10 + (temp % 10);
      temp = Math.floor(temp / 10);
    }
    // 每增加一个相同的则与原先已存在的数量（h.get(i - j)）配对 ,从而不使用排列组合就可求结果
    res = (res + (h.get(i - j) || 0)) % MOD;
    h.set(i - j, (h.get(i - j) || 0) + 1);
  }
  return res;
};