題目

難度級(jí)別：簡(jiǎn)單

統(tǒng)計(jì)所有小于非負(fù)整數(shù) n 的質(zhì)數(shù)的數(shù)量。

示例 1：

輸入：n = 10
輸出：4
解釋：小于 10 的質(zhì)數(shù)一共有 4 個(gè), 它們是 2, 3, 5, 7 。

示例 2：

輸入：n = 0
輸出：0

示例 3：

輸入：n = 1
輸出：0

提示：

0 <= n <= 5 * 106

解題思路

埃氏篩

若一個(gè)數(shù)為質(zhì)數(shù)，則它的n倍就一定是一個(gè)合數(shù)。初始化數(shù)組isPrimes，數(shù)量為n，每一項(xiàng)賦值為1。遍歷數(shù)組isPrimes，當(dāng)它為1時(shí)說(shuō)明是一個(gè)質(zhì)數(shù)，之后求出它的n倍，并賦值0。

const countPrimes = function(n) {
    const isPrimes = new Array(n).fill(1)
    let count = 0

    for(let i = 2; i < isPrimes.length; i++) {
        if (isPrimes[i]) {
            count++
            for(let j = i * i; j < n; j = j + i) {
                isPrimes[j] = 0
            }
        }
    }

    return count
};

線性篩

與埃氏篩的基礎(chǔ)上在創(chuàng)建質(zhì)數(shù)primes數(shù)組，當(dāng)在isPrimes里遇到值為1的質(zhì)數(shù)時(shí)，將其添加至primes數(shù)組。同時(shí)遍歷primes數(shù)組，因?yàn)閜rimes內(nèi)是質(zhì)數(shù)，所以乘上任何數(shù)都是合數(shù)。當(dāng)遇到 isPrimes的第i項(xiàng) % primes[j]的值為0時(shí)，后面的數(shù)之前的數(shù)已經(jīng)計(jì)算過(guò)，跳出循環(huán)。

const countPrimes = function(n) {
    const isPrimes = new Array(n).fill(1)
    const primes = []
    
    for(let i = 2; i < isPrimes.length; i++) {
        if (isPrimes[i]) primes.push(i)
        
        for(let j = 0; j < primes.length && i * primes[j] < n; j++) {
            isPrimes[i * primes[j]] = 0
            if (i % primes[j] === 0) break
        }
    }

    return primes.length
};

題目來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/count-primes