链接：计数质数
1.判断一个数是否为素数的方法
- 从
判断是否有
的因数，如果不能找到因数，则
)
def is_prime(n):
for e in range(2, n):
if n % e == 0:
return False
else:
return True
- 从
判断是否有
)
def is_prime(n):
for e in range(2, int(sqrt(n))+1):
if n % e == 0:
return False
else:
return True
2.标记小于数的全部素数
对于这个问题，可以对中每个元素使用
的算法进行判断，整体的时间复杂度为
，在本题的case中会超时。
这个问题可以使用埃式筛算法来快速找到小于的所有素数，具体流程如下
- 创建一个长度为
- 当我门找到一个素数
时，对这个素数的所有倍数，都置为False，即
这些数都是合数。这里有个优化点，即当
），
对应的
，会在之前的遍历中被置为False，因此只需要对
进行置False操作。
开始置False，当
时，便没有数可以置False，因此遍历时
。
class Solution:
def countPrimes(self, n: int) -> int:
if n < 2:
return 0
nums = [True] * n
nums[0], nums[1] = False, False
for i in range(2, int(n**0.5)+1):
if nums[i]:
for j in range(i*i, n, i):
nums[j] = False
return sum(nums)
