Skip to main content

Count Primes

Problem Description​

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

Examples​

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^6

Solution for Count Primes Problem​

Brute Force​

  • Iterate through all numbers from 2 up to n-1 (since we need to find primes less than n).
  • For each number, check if it is a prime by counting its divisors.

Implementation​

Live Editor
function primeCounter(n) {
 function isPrime(n) {
        let count = 0;
        if (n === 1) {
            return false;
        }
        for (let i = 1; i < n; i++) {
            if (n % i === 0) {
                count++;
            }
        }
        if (count > 1) {
            return false;
        }
        return true;
    }

    function countPrimes(n) {
        let count = 0;
        for (let i = 2; i < n; i++) {
            if (isPrime(i)) {
                count++;
            }
        }
        return count;
    }

  const input = 10
  const output = countPrimes(input)
  return (
    <div>
      <p>
        <b>Input: </b>{ JSON.stringify(input)}
      </p>
      <p>
        <b>Output:</b> {output.toString()}
      </p>
    </div>
  );
}
Result
Loading...

Complexity Analysis​

  • Time Complexity: O(n2)O(n^2) is the time complexity, because two nested loops are used , one is from 2 to n and second is used to check whether a number is prime or not which also takes O(n) O(n) complexity
  • Space Complexity: O(1)O(1)

Optimized Approach - Sieve of Eratosthenes Algorithm​

Intuition​

The Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given limit n. The basic idea is to iteratively mark the multiples of each prime starting from 2. By the end of the algorithm, the numbers that remain unmarked are prime.

Steps​

  • Create a list of boolean values: Initialize an array is_prime of size n with all values set to true. is_prime[i] will be true if i is a prime number, false otherwise.
  • Mark non-primes: Starting from the first prime number (2), mark all its multiples as non-prime. Move to the next number and repeat until you've processed numbers up to the square root of n.
  • Count primes: The numbers which remain marked as true in the is_prime array are primes.

Code in Different Languages​

Written by @hiteshgahanolia
function countPrimes(n) {
if (n <= 2) return 0;

// Step 1: Initialize the array with true values
let is_prime = new Array(n).fill(true);
is_prime[0] = is_prime[1] = false; // 0 and 1 are not primes

// Step 2: Mark non-primes
for (let i = 2; i * i < n; i++) {
if (is_prime[i]) {
for (let j = i * i; j < n; j += i) {
is_prime[j] = false;
}
}
}

// Step 3: Count primes
let count = 0;
for (let i = 2; i < n; i++) {
if (is_prime[i]) {
count++;
}
}
return count;
}


Complexity Analysis​

  • Time Complexity: O(N∗log(logn)) O(N*log(logn))
  • Space Complexity: O(N) O(N)

References​