[LeetCode]204. 计数质数

204. 计数质数
统计所有小于非负整数 n 的质数的数量。
示例:
输入: 10
输出: 4
解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

厄拉多塞筛法

最常见的判断n是否是质数的思路就是逐个遍历2~n^0.5之间的数能否被n整除, 若能整除则不是质数, 不能整除则是质数.
然而这个算法的时间复杂度是O(n^2), 当n特别大时肯定会超时, 在LeetCode中提交不会通过.
这时该用到厄拉多塞筛法, 实现步骤: 从2开始遍历到根号n，先找到第一个质数2，然后将其所有的倍数全部标记出来，然后到下一个质数3，标记其所有倍数，一次类推，直到根号n，此时数组中未被标记的数字就是质数。我们需要一个n-1长度的bool型数组来记录每个数字是否被标记，长度为n-1的原因是题目说是小于n的质数个数，并不包括n。

Sieve_of_Eratosthenes_animation.gif
示例代码:

class Solution(object):
  def countPrime(n):
      if n < 3:
          return 0
      prime = [1] * n
      prime[0] = prime[1] = 0
      for i in range(2, int(n**0.5) +1):
          if prime[i] == 1:
              prime[i*i:n:i] = [0]*len(prime[i*i:n:i])
      return sum(prime)