Description

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.

Analysis

It is easy to come up with the brute force method. When judging a prime number, we need to judge if there is a divisor of n from \(2\) to \(\sqrt{n}\). So the time complexity is \(O(n\sqrt{n})\).

However, we have a efficient method, Sieve of Eratosthenes. We define a boolean vector that reflects whether the number is prime. Set the initial values be true. For the number from \(2\) to \(n-1\), if one number is true, then set the multiples of it be false. In the meantime, count the number that is true.

Solution

class Solution {
    public int countPrimes(int n) {
        if(n<=2) return 0;
        int res=0;
        boolean[] pri=new boolean[n-2];
        for(int i=2;i<n;i++)
        {
            pri[i-2]=true;
        }
        for(int i=2;i<n;i++)
        {
            if(pri[i-2]==true)
            {
                res++;
                for(int j=2;i*j<n;j++)
                    pri[i*j-2]=false;
            }
        }
        return res;
    }
}

Reference

[1] https://github.com/EdwardShi92/Leetcode-Solution-Code/blob/master/CountPrimes.java

Leave a Reply

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