题目描述： 给你一个正整数N(1 <= N <= 10000000)，求{1,2,3,…,N}中质数的个数。 如N=3， 输出2.
示例： 输入： N = 1 输出： 0
分析:
参考 chenxw4tm 大佬 的思路.
用一个list（L），把不是 素数的都标成0，其他都是素数标1
有几个注意点：
1、大于6的素数都在 6 的倍数前后，所以6个一组标[1,0,0,0,1,0]*(N/6) 有些6k+1/6k+5可能不是素数，先初始化为1
2、从小到大（2,3因为条件1已经排除，从5,7……开始）不断把素数p的倍数弄成0，剩下的就是所有素数。
但是第二步有些简单的精细：
1、不需要每次用数学方法判断p是不是素数，因为L优化完前一个p以后，排在p以后，值为1的那个下标自然是下一个要优化的素数
2、优化的素数也不是2-N，二是2到根号N
3、每次优化，也不是从2p，3p这样优化，二是p*p，p*p+2p，p*p+4p……，因为p*（p-1）这项，肯定有p-1这个比p小的因子，肯定已经优化过了，而p*p+p之类都是偶数，初始化已经为0了
4、每次找下一个素数，步长设为2，不是1，因为都是奇数。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def f(N):
fir=[0,0,1,1,0,1,0]
L = [0 for _ in range(N+1)]
L[:7] = fir
if N<=6:
return sum(L[:N+1])
else:
# [1,0,0,0,1,0]*(N/6) 也就是模仿这一步
for i in range(5, N+1):
if (i-1) % 6 == 0 or (i+1) % 6 == 0:
L[i] = 1
z=5
while z<=int(N**0.5):
if L[z]==1:
for j in range(z*z,N+1,2*z):
L[j]=0
z=z+2
return sum(L)
print(f(N))