## Description

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.


## Solutions

题意就是找比 $n$ 小的质数的个数了，所谓质数就是除了 1 和其本身不能被其他整除的数。

### 1. Brute Force

想先快速实现一个暴力的版本，结果超时了：

class Solution:
def countPrimes(self, n: int) -> int:
if n <= 1:
return 0
count = 0
for i in range(1, n):
if self.isPrimes(i):
count += 1
return count

def isPrimes(self, num):
if num <= 1:
return False

for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True


### 2. 埃拉托斯特尼筛法

埃拉托斯特尼筛法就是用来解决这个问题，以此从小到大找到所有质数的倍数给全部删掉即可。

# Time: O(nloglogn)
# Space: O(n)
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
tags = [True for _ in range(n)]
tags[0], tags[1] = False, False
sqrtn = int(round(n ** 0.5))
for i in range(2, sqrtn + 1):
if tags[i]:
for j in range(i * i, n, i):
tags[j] = False

return sum(tags)
# 20/20 cases passed (500 ms)
# Your runtime beats 63.22 % of python3 submissions
# Your memory usage beats 62.07 % of python3 submissions (27.6 MB)


牛人优化之后的版本更快：

class Solution(object):

def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2:
return 0

s = [True] * n
s[0] = s[1] = False
sqrtn = int(round(n**0.5))
for i in xrange(2, sqrtn + 1):
if s[i]:
s[i*i: n: i] =  [False] * len(xrange(i*i, n, i))
return s.count(True)
# Runtime: 132 ms, faster than 98.74% of Python online submissions for Count Primes.
# Memory Usage: 34.9 MB, less than 76.32% of Python online submissions for Count Primes.