204. Count Primes.md

204. Count Primes

https://leetcode.com/problems/count-primes/description/

solution

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0
        primes = [True] * n
        ans = 0
        for i in range(2, n):
            if primes[i]:
                ans += 1
                for j in range(i * i, n, i):
                    primes[j] = False
        return ans

时间复杂度：O()
空间复杂度：O()