计数质数

统计 [2,n] 中质数的数量是一个很常见的题目，也有很多巧妙高效的做法。这里主要记录几种最优的算法。

枚举 · 优化

思路

因式分解4到8:

• 4: 1 * 4 2 * 2 4 * 1
• 5: 1 * 5 sqrt(5) * sqrt(5) 5 * 1
• 6: 1 * 6 2 * 3 sqrt(6) * sqrt(6) 3 * 2 2 * 1
• 7: 1 * 7 sqrt(7) * sqrt(7) 7 * 1
• 8: 1 * 8 2 * 4 sqrt(8) * sqrt(8) 4 * 2 8 * 1

结论

合数和质数的 sqrt 前后因式一样。以 sqrt 为界，只要能被前面数整除，该数不是质数

1
2
3
4
5
6
7
8
9

var countPrimes = function (n) {
    for(var i = 2, r = 0; i < n; i++) isPrime(i) && r++
    return r
    function isPrime(n) {
        for (var i = 2, max = Math.sqrt(n); i <= max; i++)
            if (n % i === 0) return false
        return true
    }
};

埃氏筛

思路

这是一个古老的筛素数的方法。方法如下：

• 初始化长度O(n) 的标记数组，表示这个数组是否为质数。数组初始化所有的数都是质数。
• 从 2 开始将当前数字的倍数全都标记为合数。标记到√n时停止即可。具体可以看来自维基百科的动画：

注意： 每次找当前素数 xx 的倍数时，是从x²开始的。因为如果 x>2，那么 2*x 肯定被素数2给过滤了，最小未被过滤的肯定是x²。

1
2
3
4
5
6
7
8
9
10
11
12

var countPrimes = function (n) {
    let arr = new Array(n).fill(true);
    for (let i = 2; i * i < n; i++) {
        if (arr[i]) {
            for (let j = i * i; j < n; j += i) {
                arr[j] = false
            }
        }
    }
    for (var i = 2, cnt = 0; i < arr.length; i++) arr[i] && cnt++;
    return cnt
};

参考文章

• 枚举 + 埃氏筛 + 线性筛 + 奇数筛（5行代码，4解法，超99%）
• 快来秒懂筛质数！

• ← Previous Post
• Next Post →