Count primes [Sieves of erathmus]

88.Count Primes

Math

Sieve of Eratosthenes

Problem Statement:

Given an integer n, return the count of prime numbers less than n. A prime number is a number greater than 1 that has no divisors other than 1 and itself.

Algorithm:

1. Use the Sieve of Eratosthenes to efficiently count primes:
• Initialize a boolean array isNotPrime of size n, where false means the index is a prime number.
• Iterate through numbers starting from 2 up to sqrt(n):
• If the number is already marked as not prime, skip it.
• Mark all multiples of the current number as not prime, starting from its square.
2. Count the numbers that are still marked as prime in the boolean array.
3. Return the count.

Complexity:

Time: O(n log(log(n))), where n is the input value | Space: O(n)

Java Implementation:

public int countPrimes(int n) {
    boolean[] isNotPrime = new boolean[n];
    int count = 0;

    // Iterate from 2 up to sqrt(n)
    for (int i = 2; i * i < n; i++) {
        if (isNotPrime[i]) continue;

        // Mark multiples of i as not prime
        for (int j = i * i; j < n; j += i) {
            isNotPrime[j] = true;
        }
    }

    // Count primes
    for (int i = 2; i < n; i++) {
        if (!isNotPrime[i]) count++;
    }

    return count;
}

Python Implementation:

def countPrimes(n):
    if n < 2:
        return 0

    is_not_prime = [False] * n
    count = 0

    # Iterate from 2 up to sqrt(n)
    for i in range(2, int(n ** 0.5) + 1):
        if is_not_prime[i]:
            continue

        # Mark multiples of i as not prime
        for j in range(i * i, n, i):
            is_not_prime[j] = True

    # Count primes
    for i in range(2, n):
        if not is_not_prime[i]:
            count += 1

    return count

C++ Implementation:

#include 
using namespace std;

int countPrimes(int n) {
    if (n < 2) return 0;

    vector isNotPrime(n, false);
    int count = 0;

    // Iterate from 2 up to sqrt(n)
    for (int i = 2; i * i < n; i++) {
        if (isNotPrime[i]) continue;

        // Mark multiples of i as not prime
        for (int j = i * i; j < n; j += i) {
            isNotPrime[j] = true;
        }
    }

    // Count primes
    for (int i = 2; i < n; i++) {
        if (!isNotPrime[i]) count++;
    }

    return count;
}