204. 计数质数

描述

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

链接：https://leetcode.cn/problems/count-primes

解答

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    // 当 n = 2 时， 0、1 都不是素数
    if (n <= 2) {
        return 0;
    }

    return solution2(n);
};

function solution2(n) {
    const nums = new Array(n).fill(true);

    for (let i = 2, len = Math.sqrt(n); i <= len; i++) {
        if (nums[i] === false) {
            continue;
        }

        if (isPrime(i)) {
            // 如果 i 是素数，则 i*i, i*(i+1), i*(i+2), ... 都不是素数
            for (let j = i * i; j < n; j += i) {
                nums[j] = false;
            }
        }
    }

    let count = 0;

    for (let i = 2, len = n; i < len; i++) {
        if (nums[i] === true) {
            count += 1;
        }
    }

    return count;
}

function solution1(n) {
    // 当 n = 2 时， 0、1 都不是素数
    if (n <= 2) {
        return 0;
    }

    let count = 0;

    for (let i = 2, len = n; i < len; i++) {
        if (isPrime(i)) {
            count += 1;
        }
    }

    return count;
}

function isPrime(num) {
    for (let i = 2, len = Math.sqrt(num); i <= len; i++) {
        if (num % i === 0) {
            return false;
        }
    }
    return true;
}