一.问题描述
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.
二.解题思路
最基本的方法：迭代从1~n，判断,1~根号i能否被i整除（假设i是当前迭代的数）。这个方法可以想象得到会很慢。
不过我还没在leetcode里面跑过，不知道会不会超时。
时间复杂度O(N*N)
因为之前写过类似的题目，知道求范围内的质数是有一个高效的算法的：
Sieve of Eratosthenes-埃拉托斯特尼筛法，简称埃氏筛。以前的博客好像写过这个算法，不大记得是哪一个了，就再写一遍吧。。。。
简单来说记住一点，任何一个合数都有质因子，所以如果把质数的倍数全部去掉（最初只知道2是质数），那么剩下的就是质数。
然后我们一开始初始化，假设所有数都是质数，数组值全为1，
1.i从2开始迭代（我们知道2是第一个质数），然后2的倍数全为合数，设置为0（相当于去掉了）
2.读取剩下数中最小的数（假设我们把那些数已经去掉了，实现的时候是设置为0，相当于找第一个为1的数），从i+1开始迭代，如果i+1为1（说明是质数），结果+1，(i+1)的倍数全为合数，设置为0,重复直到n。
可能有人会问为啥i+1为1的话就一定为质数，简单说明一下，
因为我们是顺序处理的，如果i+1值为1并且为合数，这就说明i+1有一个小于它自己的质因子j， j<i+1，
如果存在这样一个质因子j，那么在之前迭代到j的时候，就会设置它的倍数为0，然后i+1是j的倍数，所以i+1不可能值为1.
所以顺序处理是关键。
3.最后求和数组中值为1的数量就是结果。
注意:0和1记得提前赋值，不是质数。
时间复杂度:(NlogN)
还不懂的话给一篇博客参考详细的算法：找质数算法之埃拉托色尼筛选法（Sieve of Eratosthenes算法）
实现优化：
对于实现来说我们可以进一步优化，
我们现在的做法是，如果i是质数，那么2*i,3*i,4*i分别设置为0，其实这是有重复操作的。
我们只需要从i*i开始就好了。
因为2*i,3*i,4*i,这些小于i*i的数，都会在迭代到i之前就被处理了，比如说2*i，在迭代到2的时候，2的倍数就全被设置为0了。
时间复杂度:O(logN*logN)。
更多leetcode算法题解法: 专栏 leetcode算法从零到结束 或者 leetcode 解题目录 Python3 一步一步持续更新～
三.源码
普通的那个方法我就没有实现，
版本一是不用切片自己写while，版本二是没有优化的，版本三是优化的，运行大概时间写在注释里。
#version 1 1300ms
#attention: in this version, if a number is a prime, the vaule in array is 0 not 1
class Solution:def countPrimes(self, n: int) -> int:if n==0:return 0rst=0n_primes=[0]*ni=1while i<n-1:i+=1if n_primes[i]==1:continueelse:rst+=1t=iwhile t+i<=n-1:t+=in_primes[t]=1return rst#version2 430ms
class Solution:def countPrimes(self, n: int) -> int:if n<=2:return 0n_primes=[1]*nn_primes[0],n_primes[1],i=0,0,2while i<n:if n_primes[i]==1:n_primes[i+i:n:i]=[0]*((n-i-1)//i)i+=1return sum(n_primes)#version3 120msdef countPrimes(self, n: int) -> int:if n<=2:return 0n_primes=[1]*nn_primes[0],n_primes[1],i=0,0,2while i*i<n:if n_primes[i]==1:n_primes[i*i:n:i]=[0]*((n-1-i*i)//i+1)i+=1return sum(n_primes)