Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.Input: n = 0
Output: 0Last updated
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
}