题目链接:leetcode-cn.com/problems/co…
看到这个题目,一般人很容易就能想到使用循环,通过暴力遍历的方式检查每一个数是否为质数,并进行计数。
但是这种方法的算法复杂度过高,对于小范围搜索还好,如果是从百万甚至千万的数字中找出所有的质数,这种方法的劣势将极其明显。那我们可以使用埃拉托斯特尼筛法进行质数的查找。
埃拉托斯特尼筛法
埃拉托斯特尼筛法,简称埃氏筛,也称素数筛。这是一种简单且历史悠久的筛法,用来找出一定范围内所有的素数。所使用的原理是从 2 开始,将每个素数的各个倍数,标记成合数。
一个素数的各个倍数,是一个差为此素数本身的等差数列。此为这个筛法和试除法不同的关键之处,后者是以素数来测试每个待测数能否被整除。
埃拉托斯特尼筛法是列出所有小素数最有效的方法之一,其名字来自于古希腊数学家埃拉托斯特尼,并且被描述在另一位古希腊数学家尼科马库斯所著的《算术入门》中。
本算法的核心思想是:给出要筛选数值的范围 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;
};
复制代码
√ 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)
参考资料:
更多题解
本人水平有限,欢迎交流分享你的想法,欢迎大佬批评指正。
扫描下方二维码,关注微信公众号「技术漫谈」,订阅更多精彩内容。