Counting Primes

Count Primes

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

Sieve of Eratosthenes Algorithm

The Sieve of Eratosthenes is a classical algorithm for finding all prime numbers up to a specified limit. It works by iteratively marking the multiples of each prime number starting from 2, as composite numbers.

Complexity Analysis:

• Time: $O(n\log \log n)$ — significantly faster than naive $O(n\sqrt{n})$ approaches
• Space: $O(n)$ for the boolean array

Algorithm Steps:

1. Create a boolean array is_prime of size n initialized to true
2. Mark indices 0 and 1 as false (neither 0 nor 1 are prime)
3. For each number $i$ from 2 to $\sqrt{n}$: if is_prime[i] is true, mark all multiples of $i$ as false
4. Count the remaining true values in the array

Solution

 
#include <cmath>
#include <vector>
using namespace std;
 
class Solution {
public:
  int countPrimes(int n) {
    if (n <= 1) // There are no primes less than 2
      return 0;
    vector<bool> isPrime;
    // initialize the isPrime vector with true values
    for (int i = 0; i < n; i++) {
      isPrime.push_back(true);
    }
    // 0 and 1 are not prime numbers
    isPrime[0] = false;
    isPrime[1] = false;
    // Sieve of Eratosthenes
    for (int p = 2; p < sqrt(n); p++) {
      if (isPrime[p])
        for (int i = p * p; i < n; i += p)
          isPrime[i] = false;
    }
    // Count the number of primes
    int primes = 0;
    for (int i = 0; i < n; i++) {
      if (isPrime[i]) {
        primes++;
      }
    }
    return primes;
  }
};

Optimizations

1. Vector Initialization

Use the vector constructor directly instead of a loop:

vector<bool> isPrime(n, true);

2. Loop Bound Optimization

Replace sqrt(n) with p * p < n to avoid expensive floating-point operations:

for (int p = 2; p * p < n; p++) {
    if (isPrime[p]) {
        for (int i = p * p; i < n; i += p) {
            isPrime[p] = false;
        }
    }
}

3. Space Optimization

Run the Sieve only on odd numbers, reducing space by half. Account for 2 separately:

vector<bool> isPrime((n + 1) / 2, true);
isPrime[0] = false; // 1 is not prime
for (int p = 3; p * p < n; p += 2)
{
    if (isPrime[p / 2]) {
        for (int i = p * p; i < n; i += 2 * p) {
            isPrime[i / 2] = false;
        }
    }
}
int primes = 1; // Count 2 as prime
for (int i = 1; i < isPrime.size(); i++) {
    if (isPrime[i]) {
        primes++;
    }
}
return primes;