Counting Primes

Count Primes

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

Algorithm

Sieve of Eratosthenes is an efficient algorithm to find all prime numbers up to a given limit. The algorithm works by iteratively marking the multiples of each prime number starting from 2. The time complexity is O(n log log n) and the space complexity is O(n). The algorithm works as follows:

1. Create a boolean array is_prime of size n initialized to true.
2. Set is_prime[0] and is_prime[1] to false since 0 and 1 are not prime.
3. For each number i from 2 to the square root of n, if is_prime[i] is true, mark all multiples of i as false.
4. Count the number of true values in the is_prime array, which gives the count of prime numbers less than n.

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;
  }
};

Optimisation

The first optimization is to initialize isPrime in a different way, using a vector constructor that takes the size and initial value. This avoids the need for a loop to fill the vector with true values.

vector<bool> isPrime(n, true);

The second optimization is to set the upper limit of the outer loop to p*p < n instead of p<sqrt(n). This is because sqrt() is inefficient for large numbers and p*p is faster.

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

The third optimisation is to run the Sieve only for odd numbers in a array of size n/2 and then just add 1 to the final count to account for the number 2.

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;