import (
	"math"
)

func countPrimes(n int) int {
	notPrime := make([]bool, n+1)
	sqrtN := int(math.Sqrt(float64(n)))
	for k := 2; k <= sqrtN; k++ {
		if notPrime[k] {
			continue
		}
		for m := 2*k; m < n; m += k {
			notPrime[m] = true
		}
	}
	cnt := 0
	for i := 2; i < n; i++ {
		if !notPrime[i] {
			cnt++
		}
	}
	return cnt
}