Count Primes

Problem

Given an integer n, return the number of prime numbers that are strictly less than n.

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

Constraints:

0 <= n <= 5 * 10⁶

Solution

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    let prime = Array(n).fill(true);
    let count = 0;
    for (let i = 2; i < n; ++i) {
        if (prime[i]) {
            count++;
            for (let j = i * i; j < n; j += i) {
                prime[j] = false;
            }
        }
    }
    return count;
};

Use array prime to keep track of which numbers from the range 0 to n - 1 are prime. Iterate through all numbers up to n. If the current number is prime, increment count and mark all multiples of this value in the rest of the array as non-prime.

Problem​

Solution​

Problem

Solution