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

Today, We are going to discuss various approaches to find all primes numbers for a given range. Discovering Sieve of Eratosthenes.

Approach  1

This is the simple approach in which just check one by one each number.

We use two loops. 

First for reading each number. Second for checking if the number is prime or not. Checking number is prime – If  no. is not divisible by any number. from range [2,n/2].

Program in C++

int countPrimes(int n) {    
       int count=0; 
       // Check for 1 and 0 as they are not prime.   
       if(n<2)
       {
           return 0;
       }
        else
        {
            //Start from i=2 as it is the smallest non negative prime number. 
            int i=2;
            while(i<n)
            {
               //Create a flag variable k that checks if no. is prime or not.  
               int k=0;
               int j=2;
               //Now for each value of i check for range [2,n/2] if it is divisible or not if yes set flag
               //k=1 and break loop.   
               while(j<=i/2)
               {
                   //If i%j==0 then i is composite.
                   if(i%j==0)
                   {
                       k++;
                       break;
                   }
                   j++;
               }
                //If the flag value remains zero then the number was prime. Count no. as prime.
                if(k==0)
                {
                 count++;
                }
                i++;
            }
        }
        //return number of counted number.
        return count;
    }

Time Complexity of the above approach is O(n2). Can we do better?

Approach 2

You may notice that for each value of i we do not need to check for each value of j for range [ 2 , i /2 ].

Consider a number n. If n is divisible by some number p. Then n = p x q. Where q ≤ p .

If a number is not divisible by 2,3,any prime no. which is < √n . The number must be prime.

How to find p?

If n is divisible by p then p ≤√n . For eg n=121. Range of p will be [ 2 , Smallest integer square ≤ ] i.e [ 2 , 11 ].

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

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

Time Complexity of the above approach is O(n1.5). Can we still do better?

The Sieve of Eratosthenes comes into action. Sieve of Eratosthenes is an ancient algorithm for counting the number of primes for a given range. 

It works on simple logic i.e if a number is not divisible by any prime number then it is prime.

In this algorithm we create an array of size of the given range and mark each number starting from 2 up to n (Excluding n).

We start from 2 and mark all numbers that are divisible by 2. Then the same is done for 3.Now we come to number 4 we do not need to check for number 4. All numbers divisible by 4 are already checked by 2.  So we can skip 4 just by checking if it is checked already then skip to next.

Checking for 5 does not require to start from 5 X 2 as it has already been checked by 2. In Fact all numbers less than 5 x 5 are checked already. So for number p we start from p^2 and continue p^2 + p, p^2 + 2p, p^2 + p,…

Where do we end we can end this when p^2+np ≤ √n  .  4.

public int countPrimes(int n) {
   boolean[] isPrime = new boolean[n];
   for (int i = 2; i < n; i++) {
      isPrime[i] = true;
   }
   // Loop's ending condition is i * i < n instead of i < sqrt(n)
   // to avoid repeatedly calling an expensive function sqrt().
   for (int i = 2; i * i < n; i++) {
      if (!isPrime[i]) continue;
      for (int j = i * i; j < n; j += i) {
         isPrime[j] = false;
      }
   }
   int count = 0;
   for (int i = 2; i < n; i++) {
      if (isPrime[i]) count++;
   }
   return count;
}

The Sieve of Eratosthenes uses an extra O(n) memory and its runtime complexity is O(n log log n). For the more mathematically inclined readers, you can read more about its algorithm complexity on Wikipedia.

Leave a Comment

Your email address will not be published. Required fields are marked *

Close Bitnami banner
Bitnami