O(n) solution with Detailed Explanation of Sieve Of Eratosthenes


  • 1
    R

    This is one of the very simple problems which can be solved using Sieve of Eratosthenes. The logic of the sieve of Eratosthenes is pretty simple. When we are given a number and asked to find all the prime numbers till that number or count the number of prime numbers we can use the algorithm.

    We keep a simple boolean array mapped to the integers to denote whether the number denoted by its index is prime or not. Now we iterate from 2 through the number and mark all the factors of that number as not prime. Now once we iterate through all the numbers, all the indices at which the value is set to false are prime numbers, because you never visited them through any other number. Meaning they are not divisible any number. This core logic has been altered a little to actually count the number of prime numbers.

    NOTE: A prime number is defined as a number which is greater than one and can only be divided by itself and one.

    Here is the accepted code:

    public int countPrimes(int n) {
            
            if(n <= 2 ){
                return 0;
            }
            
            
            int count = n-2;
            boolean[] divisible = new boolean[n];
            
            for(int i=2; i< n;i++){
                if(divisible[i]){
                    continue;
                }
                
                for(int j=i;j < n;j = j+i){
                    if(!divisible[j] && j != i){
                        divisible[j] = true;
                        --count;
                    }
                }
            }
            
            return count;
        }
    

    Let me know your thoughts


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.