计算质数-简单
难度：简单
题目描述：
统计所有小于非负整数 *n *的质数的数量。
示例：
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
1
2
3
2
3
解题思路：在寻找素数时，采用了一种与众不同的方法：先将 2－N 的各数放入表中，然后在 2 的上面画一个圆圈，然后划去 2 的其他倍数；第一个既未画圈又没有被划去的数是 3，将它画圈，再划去 3 的其他倍数；现在既未画圈又没有被划去的第一个数是 5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止。
这时，表中画了圈的以及未划去的那些数正好就是小于 N 的素数。
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
2
3
4
5
6
7
8
9
10
11
12
13
14
15