Count Primes

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

You may view the full question here.

Approach 1: Let’s start with the most obvious one —

//Approach 1:
//Runtime: 465ms
//Memory usage: 32.8MB
class Solution {
    public int countPrimes(int n) {
        int count = 0;
        for(int i = 2; i<n; i++){
            if(isPrime(i)){
                count++;
            }
        }
        return count;
    }
    
    private boolean isPrime(int n) {
        int d = 2;
        int root = (int) Math.sqrt(n);
        while(d<=root){
            if(n%d==0){
                return false;
            }
            d++;
        }
        return true;
    }
}

Approach 2: In approach 1, the logic to determine if a number is prime or not involved us checking the divisibility of the number with divisors starting from 2 to square root of that number.

The divisibility check basically requires us to check with only prime divisors. To do so, we can use a list to store all the primes.

//Approach 2:
//Runtime: 151ms
//Memory usage: 38MB
class Solution {
    List<Integer> primes = new ArrayList();
    int count = 0;
    
    public int countPrimes(int n) {
        primes = new ArrayList();
        count = 0;
        for(int i = 2; i<n; i++){
            isPrime(i);
        }
        return count;
    }
    
    private boolean isPrime(int n) {
        int root = (int) Math.sqrt(n);
        if(count==0){
            int d = 2;
            while(d<=root){
                if(n%d==0){
                    return false;
                }
                d++;
            }
        } else {
            
            for(int i = 0; i<count && primes.get(i)<=root; i++){
                if(n%primes.get(i)==0){
                    return false;
                }
            }
        }
        count++;
        primes.add(n);
        return true;
    }
}

Approach 3: Let’s borrow some ideas from some ‘Great Minds’. This approach uses — Sieve of Eratosthenes. (Do check the wiki page!)

This algorithm eliminates all the composite numbers, so that you are finally left with only the prime ones. We start with a number, if it is prime, then we mark all its multiples. We do this iteratively.

A little optimization would be to only check till the square root of ‘n’, as the numbers greater than this will have multiples greater than ‘n’.

//Approach 3:
//Runtime: 9ms
//Memory usage: 34.5MB
class Solution {
    public int countPrimes(int n) {
        if (n <= 2)
  return 0;
 
 // init an array to track prime numbers
 boolean[] composite = new boolean[n];
 
    //We can stop the loop at the square root of 'n'
    //This is because the numbers greater than this square root
    //will only have multiples that are greater than 'n'
 for (int i = 2; i <= Math.sqrt(n - 1); i++) {
        //Check if the current number is a prime
  if (!composite[i]) {
            //Account for all the multiples of this prime
   for (int j = i + i; j < n; j += i)
    composite[j] = true;
  }
 }
 
 int count = 0;
 for (int i = 2; i < n; i++) {
  if (!composite[i])
   count++;
 }
 
 return count;
    }
}

Find more posts here.

Cheers & Chao!