204. Count Primes – Leetcode Solutions

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

class Solution:
    def countPrimes(self, n: int) -> int:
        # Edge case: If n is less than 2, there are no prime numbers
        if n < 2:
            return 0
        
        # Initialize a boolean array to keep track of prime numbers
        # At the start, we assume all numbers from 0 to n-1 are prime (True)
        is_prime = [True] * n
        
        # We know 0 and 1 are not prime numbers
        is_prime[0] = is_prime[1] = False
        
        # Start from the first prime number, which is 2
        for i in range(2, int(n**0.5) + 1):
            if is_prime[i]:  # If i is still marked as prime
                # Mark all multiples of i as non-prime (False)
                for j in range(i * i, n, i):
                    is_prime[j] = False
        
        # The sum of the 'True' values in the is_prime array gives the count of primes
        return sum(is_prime)

/**
 * @param {number} n
 * @return {number}
 */
var countPrimes = function(n) {
    // Edge case: If n is less than 2, there are no prime numbers
    if (n < 2) {
        return 0;
    }
    
    // Initialize an array to track prime numbers
    // We assume initially that all numbers from 0 to n-1 are prime (true)
    let isPrime = new Array(n).fill(true);
    
    // We know 0 and 1 are not prime numbers
    isPrime[0] = isPrime[1] = false;
    
    // Start from the first prime number, which is 2
    for (let i = 2; i * i < n; i++) {
        if (isPrime[i]) {  // If i is still marked as prime
            // Mark all multiples of i as non-prime (false)
            for (let j = i * i; j < n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    
    // Count the number of true values in the isPrime array
    let count = 0;
    for (let i = 0; i < n; i++) {
        if (isPrime[i]) {
            count++;
        }
    }
    
    return count;
};

class Solution {
    public int countPrimes(int n) {
        // Edge case: If n is less than 2, there are no prime numbers
        if (n < 2) {
            return 0;
        }
        
        // Initialize a boolean array to track prime numbers
        // We assume initially that all numbers from 0 to n-1 are prime (true)
        boolean[] isPrime = new boolean[n];
        for (int i = 0; i < n; i++) {
            isPrime[i] = true;
        }
        
        // We know 0 and 1 are not prime numbers
        isPrime[0] = isPrime[1] = false;
        
        // Start from the first prime number, which is 2
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {  // If i is still marked as prime
                // Mark all multiples of i as non-prime (false)
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Count the number of true values in the isPrime array
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        
        return count;
    }
}

public class Solution {
    public int CountPrimes(int n) {
        // Edge case: If n is less than 2, there are no prime numbers
        if (n < 2) {
            return 0;
        }
        
        // Initialize a boolean array to track prime numbers
        // We assume initially that all numbers from 0 to n-1 are prime (true)
        bool[] isPrime = new bool[n];
        for (int i = 0; i < n; i++) {
            isPrime[i] = true;
        }
        
        // We know 0 and 1 are not prime numbers
        isPrime[0] = isPrime[1] = false;
        
        // Start from the first prime number, which is 2
        for (int i = 2; i * i < n; i++) {
            if (isPrime[i]) {  // If i is still marked as prime
                // Mark all multiples of i as non-prime (false)
                for (int j = i * i; j < n; j += i) {
                    isPrime[j] = false;
                }
            }
        }
        
        // Count the number of true values in the isPrime array
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (isPrime[i]) {
                count++;
            }
        }
        
        return count;
    }
}