# 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)
```