> For the complete documentation index, see [llms.txt](https://code-snippets.hbamithkumara.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code-snippets.hbamithkumara.com/leetcode/problems/201-300/count-primes.md).

# 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](https://www.geeksforgeeks.org/count-primes-ranges/)
* [Leetcode](https://leetcode.com/problems/count-primes/)
* [ProgramCreek](https://www.programcreek.com/2014/04/leetcode-count-primes-java/)
* YouTube

### **Examples**

{% tabs %}
{% tab title="Example 1" %}
**Input:** n = 10

**Output:** 4

**Explanation:** There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
{% endtab %}

{% tab title="Example 2" %}
**Input:** n = 0

**Output:** 0
{% endtab %}

{% tab title="Example 3" %}
**Input:** n = 1

**Output:** 0
{% endtab %}
{% endtabs %}

### **Solutions**

{% tabs %}
{% tab title="Solution 1" %}

```java
/**
 * 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;
    }
}
```

{% endtab %}

{% tab title="Solution 2" %}

```java
/**
 * 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;
    }
}
```

{% endtab %}
{% endtabs %}

### **Follow up**

*