题目：
给定整数
n，返回 所有小于非负整数n的质数的数量 。来源：力扣（LeetCode）
链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
示例：
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：输入：n = 0
输出：0
示例 3：输入：n = 1
输出：0
解法：
采用Sieve of Eratosthenes，核心思想是数2,3,4，……，n，依次去除2的倍数，3的倍数，4的倍数……
举例，假设2,3,4，……，100，先把2的倍数全部去掉，从2的平方开始去，剩下2,3,5,7,9，……，99。接着把3的倍数全部去掉，从3的平方开始去，剩下2,3,5,7，……，97。从平方开始去的原因是，一个合数可能由多组因数组成，要么两个因数相同，要么一大一小，对于一大一小的情况，理想的处理方式是，遇到小因数的时候去掉合数，遇到大因数的时候不再考虑。而从平方开始去，有助于实现这一思路。比如6，遍历2的时候已经去掉了，所以遍历3的时候没必要考虑，直接从9开始去。因为最小的因数是2并且2的2倍和平方相等，所以不会有遗漏，所以没必要考虑3*2,4*3等类似情况，直接从3*3,4*4开始去。
因为每次从平方开始去，所以只需要遍历到n的开方就可以了。
代码：
class Solution: def countPrimes(self, n: int) -> int: if n < 3: return 0 nums = [0, 0] + [1] * (n - 2) for index in range(2, int(n ** 0.5) + 1): if nums[index]: nums[index * index::index] = [0] * len(nums[index * index::index]) return sum(nums)
