C++ Coding Exercise - Count Primes | Algorithms, Blockchain and Cloud

Count the number of prime numbers less than a non-negative number, n.

Submit your solution to: https://leetcode.com/problems/count-primes/

Naive Solution

The first solution is straightforward, a prime number is a number that has only 1 and itself factor. Note that 1 is not a prime number and 2 is the only prime number that is a even number.

bool isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i < n; i ++) {
     if (n % i == 0) return false;
  }
  return true;
}

bool isPrime(int n) {
  if (n <= 1) return false;
  for (int i = 2; i < n; i ++) {
     if (n % i == 0) return false;
  }
  return true;
}

To count the number is easy.

  int c = 0;
  for (int i = 2; i < n; i ++) {
    if (isPrime(i)) c ++;
  }

  int c = 0;
  for (int i = 2; i < n; i ++) {
    if (isPrime(i)) c ++;
  }

However, the above O(n) isPrime check is not efficient. With counting O(n) that makes the overall complexity O(n^2) which is bad when n gets large. We know that the number must not be divisible by any number > n / 2, and we can replace i < n with i < n/2.

Further, we know that we only need to consider factors up to √n because, if n is divisible by number p, then n = p × q and since p ≤ q, we know p ≤ √n.

Improvement O(n^1.5)

Based on above improvement, we can have the improved version, which is:

int count(int n) {
   int count = 0;
   for (int i = 1; i < n; i++) {
      if (isPrime(i)) count++;
   }
   return count;
}
 
bool isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}

int count(int n) {
   int count = 0;
   for (int i = 1; i < n; i++) {
      if (isPrime(i)) count++;
   }
   return count;
}

bool isPrime(int num) {
   if (num <= 1) return false;
   // Loop's ending condition is i * i <= num instead of i <= sqrt(num)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i <= num; i++) {
      if (num % i == 0) return false;
   }
   return true;
}

Sieve of Eratosthenes

Sieve of Eratosthenes, is one of the most efficient ways to find all of the smaller primes.

As the following GIF animation shows, each time, a number in the list that is prime will be used to filter out numbers that are not prime (composite) by multiples of the current prime number.

Sieve_of_Eratosthenes_animation C++ Coding Exercise - Count Primes algorithms c / c++ leetcode online judge math

Sieve_of_Eratosthenes_animation (Sieve of Eratosthenes: algorithm steps for primes below 121. "Sieve of Eratosthenes Animation" by SKopp is licensed under CC BY 2.0.)

The algorithm of finding prime uses an O(n) memory and the runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#Algorithm_complexity.

For example, all multiples of 5 such as 5 × 2 = 10, 5 × 3 = 15, 5 × 4 = 20, 5 × 5 = 25, ... can be set to composite numbers. There is a slight optimization here, we do not need to start from 5 × 2 = 10. We can mark off multiples of 5 starting at 5 × 5 = 25, because 5 × 2 = 10 was already marked off by multiple of 2, similarly 5 × 3 = 15 was already marked off by multiple of 3. Therefore, if the current number is p, we can always mark off multiples of p starting at p2, then in increments of p: p2 + p, p2 + 2p, ...

class Solution {
public:
    int countPrimes(int n) {
        bool *isprime = new bool[n + 1];
        for (int i = 2; i < n + 1; i ++) {
            isprime[i] = true;
        }
        for (int i = 2; i * i < n; i ++) {
            if (isprime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isprime[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i < n; i ++) {
            if (isprime[i]) {
                cnt ++;
            }
        }
        return cnt;
    }
};

class Solution {
public:
    int countPrimes(int n) {
        bool *isprime = new bool[n + 1];
        for (int i = 2; i < n + 1; i ++) {
            isprime[i] = true;
        }
        for (int i = 2; i * i < n; i ++) {
            if (isprime[i]) {
                for (int j = i * i; j < n; j += i) {
                    isprime[j] = false;
                }
            }
        }
        int cnt = 0;
        for (int i = 2; i < n; i ++) {
            if (isprime[i]) {
                cnt ++;
            }
        }
        return cnt;
    }
};