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

# Count Primes

Count the number of prime numbers less than a non-negative number **n.**

埃拉托斯特尼筛法： <http://open.163.com/movie/2012/10/0/6/M99VJKUHC_M9ENDUB06.html>

首先使所有数都为prime（true），循环所有数，使此数平方以后的所有此数的倍数都为false

```
class Solution(object):
    def countPrimes(self, n):
        """
        :type n: int
        :rtype: int
        """
        isPrime = [True] * max(n, 2)
        isPrime[0], isPrime[1] = False, False
        x = 2
        while x*x < n:
            if isPrime[x]:
                p = x*x
                while p < n:
                    isPrime[p] = False
                    p += x
            x += 1
        return sum(isPrime)
```