204. Count Primes

LeetCode 204. Count Primes

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

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