class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n<2:
return 0
A=[True]*n
for i in range(2,int(n**0.5)+1):
if A[i]:
for j in range(i**2,n,i):
A[j]=False
return sum(A)-2
https://www.youtube.com/watch?v=whwlDCExMpY
def eratosthenes(n):
P = [i for i in range(2, n+1)]
p = 0
while True:
for i in P[p + 1:]:
if i % P[p] == 0:
P.remove(i)
if P[p]**2 >= P[-1]:
break
p += 1
return P https://zh.wikipedia.org/wiki/埃拉托斯特尼筛法
