LeetCode JavaScript

# 204. 计数质数：埃拉托斯特尼筛法

tags:

  • hash-table
  • math

# 题目链接

https://leetcode-cn.com/problems/count-primes/

看到这个题目，一般人很容易就能想到使用循环，通过暴力遍历的方式检查每一个数是否为质数，并进行计数。但是这种方法的算法复杂度过高，对于小范围搜索还好，如果是从百万甚至千万的数字中找出所有的质数，这种方法的劣势将极其明显。那我们可以使用埃拉托斯特尼筛法进行质数的查找。

# 埃拉托斯特尼筛法

本算法的核心思想是：给出要筛选数值的范围 n，找出 √𝑛 以内的素数 p1, p2..., p𝑘。先用 2 去筛，即把 2 留下，把 2 的倍数剔除掉；再用下一个素数，也就是 3 筛，把 3 留下，把 3 的倍数剔除掉；接下去用下一个素数 5 筛，把 5 留下，把 5 的倍数剔除掉；不断重复下去……

如下图所示：

下面是本算法的实现代码：

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    let count = 0;
    let signs = new Uint8Array(n);

    for (let i = 2; i < n; i++) {
        if (!signs[i - 1]) {
            count++;

            for (let j = i * i; j <= n; j += i) {
                signs[j - 1] = true;
            }
        }
    }
    return count;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

√ Accepted

  • 20/20 cases passed (76 ms)
  • Your runtime beats 99.23 % of javascript submissions
  • Your memory usage beats 86.67 % of javascript submissions (36.9 MB)
  • 时间复杂度：O(n * loglog n)
  • 空间复杂度：O(n)

参考资料：

←