204. Count Primes

Description

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

Constraints

• 0 <= n <= 5 * 106

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    public int countPrimes(int n) {
        if(n <= 2) return 0;
        
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        
        int count = n-2;
        
        for(int i = 2; i*i < n; i++) {
            if(!isPrime[i]) continue;
            for(int j = i; i*j < n; j++) {
                if(isPrime[i*j]) {
                    isPrime[i*j] = false;
                    count--;
                }
            }
        }
        
        return count;
    }
}

Solution 2

/**
 * Time complexity : 
 * Space complexity : 
 */
 
 class Solution {
    public int countPrimes(int n) {
        if(n <= 2) return 0;
        
        boolean[] isPrime = new boolean[n];
        Arrays.fill(isPrime, true);
        
        int count = n/2;
        
        for(int i = 3; i*i < n; i += 2) {
            if(!isPrime[i]) continue;
            for(int j = i*i; j < n; j += i*2) {
                if(isPrime[j]) {
                    isPrime[j] = false;
                    count--;
                }
            }
        }
        
        return count;
    }
}

Follow up