> For the complete documentation index, see [llms.txt](https://txfs19260817.gitbook.io/leetcode-go-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/204.-count-primes.md).

# 204. Count Primes

## LeetCode [204. Count Primes](https://github.com/txfs19260817/LeetCode-Go/blob/master/solutions/title/README.md)

### Description

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

**Constraints:**

* `0 <= n <= 5 * 10^6`

### Tags

Hash Table, Math

### Solution

See Wikipedia (Reference).

### Complexity

* Time complexity: $$O(n\log(\log(n)))$$
* Space complexity: $$O(n)$$

### Code

```go
func countPrimes(n int) int {
	ans, isPrime := 0, make([]bool, n) // an array of Boolean values, indexed by 2 to n,
	for i := 2; i < n; i++ { // initially [2:n) set to true
		isPrime[i] = true
	}
	for i := 2; i*i < n; i++ {
		if isPrime[i] { // count up from the smallest marked prime
			for j := i * i; j < n; j += i { // for j = i^2, i^2+i, i^2+2i, ..., < n
				isPrime[j] = false
			}
		}
	}
	for _, n := range isPrime { // count prime numbers
		if n == true {
			ans++
		}
	}
	return ans
}
```

## Reference

1. <https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes>