Day 20.2.txt

204. Count Primes
Easy

3506

838

Add to List

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

 

Example 1:

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

Input: n = 0
Output: 0
Example 3:

Input: n = 1
Output: 0
 

Constraints:

0 <= n <= 5 * 106



class Solution {
    public int countPrimes(int n) {
        boolean k[]=new boolean[n];
        Arrays.fill(k,true);
        int i,j,c=0;
        for(i=2;i<Math.sqrt(n);i++)
        {
            if(k[i])
            {
                for(j=i*i;j<n;j+=i)
                {
                    k[j]=false;
                }
            }
        }
        for(i=2;i<n;i++)
        {
            if(k[i])
                c++;
        }
        return c;
    }
}