Count Primes Explained

Problem Statement

Given an integer n, count the number of prime numbers less than n. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. This problem tests your ability to efficiently identify prime numbers up to a given limit, often using the Sieve of Eratosthenes algorithm for optimal performance.

Example

Input: n = 10

Output: 4

Explanation: The prime numbers less than 10 are 2, 3, 5, and 7.

Code

public class Solution {
    public int countPrimes(int n) {
        boolean[] notPrime = new boolean[n];
        int count = 0;
        for (int i = 2; i < n; i++) {
            if (!notPrime[i]) {
                count++;
                for (int j = i * 2; j < n; j += i) {
                    notPrime[j] = true;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.countPrimes(10)); // 4
    }
}
            

def count_primes(n):
    if n < 2:
        return 0
    not_prime = [False] * n
    count = 0
    for i in range(2, n):
        if not not_prime[i]:
            count += 1
            for j in range(i * 2, n, i):
                not_prime[j] = True
    return count

# Example usage
print(count_primes(10))  # 4
            

function countPrimes(n) {
    if (n < 2) return 0;
    const notPrime = new Array(n).fill(false);
    let count = 0;
    for (let i = 2; i < n; i++) {
        if (!notPrime[i]) {
            count++;
            for (let j = i * 2; j < n; j += i) {
                notPrime[j] = true;
            }
        }
    }
    return count;
}

// Example usage
console.log(countPrimes(10)); // 4
            

Explanation

• Create a boolean array to mark non-prime numbers, initially assuming all numbers are prime.
• Start from 2, the smallest prime number, and iterate up to n.
• If a number is not marked as non-prime, increment the count and mark its multiples as non-prime.
• Skip numbers already marked to optimize the process.
• Return the total count of primes found.

Note