# 204\_Count Primes

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.
```

## Solution 1: brute force

**Idea**:

* Loop over every number from 2 to `n-1` and check if it is prime.
* To check if a number `i` is prime, check if it is divisible by a number from 2 to **the square root** of `i`. If yes, it is not prime.
* Why use the square root of `i`? Because if `i` has a divisor other than 1 and itself, it must also have a divisor that is no greater than its square root. 

**Time complexity**: $$O(n\*\sqrt{n})$$

**Space complexity**: $$O(1)$$

```python
def countPrimes(n):
    """
    :type n: int
    :rtype: int
    """
    # corner cases
    if n <= 1:
        return 0    

    result = 0
    for i in range(2, n):
        flag = 0
        for j in range(2, int((i+1) ** 0.5 + 1)):
            if i % j == 0:
                flag = 1
                break
        if flag == 0:
            result += 1
    return result
```

## Solution 2

Reference: Sieve of Eratosthenes <https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>

**Idea**:

* Exclude the multiples of primes
* Only need to loop over from item 2 to square root of n

**Time complexity**: $$O(n \log{\log{n}}) = O(\frac{n}{2} +\frac{n}{3} + \frac{n}{5} + \cdots)$$

**Space complexity**: $$O(n)$$

```python
def countPrimes(n):
    """
    :type n: int
    :rtype: int
    """
    # corner cases
    if n < 2:
        return 0

    # flag for each item
    is_prime = [0, 0] + [1] * (n-2)

    # loop over from item 2 to the square root of n
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i] == 1:
            is_prime[i * i:n:i] = [0] * len(is_prime[i * i:n:i])
    return sum(is_prime)
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lei-d.gitbook.io/leetcode/math/204count-primes.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.