题目
- 给定整数 n ，返回 所有小于非负整数 n 的质数的数量
示例 1：
输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2：
输入：n = 0
输出：0
示例 3：
输入：n = 1
输出：0
法一、暴力法
- 超时：时间复杂度是O(n^2)
class Solution:
def countPrimes(self, n: int) -> int:
count=0
if n==1 or n==0:
return 0
for i in range (2,n): #遍历从2到n-1的所有数，这些数将被依次判断是否为质数。
for j in range (2,i): #对于每个待判断的数i，内层循环从2到i-1遍历，用j作为除数进行判断。
if i%j == 0: #如果i能被j整除，说明i不是质数，跳出内层循环。
break
else: #如果内层循环正常结束，说明i不能被任何一个j整除，说明i是质数，计数器count加1。
count+=1
return count
法二、埃拉托斯特尼筛法（Sieve of Eratosthenes）
- 挨个判断是不是质数，如果是质数则把该数的倍数都标注为质数
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
# 初始化一个布尔数组，用于标记数字是否为质数
is_prime = [True] * n
is_prime[0] = is_prime[1] = False # 0和1不是质数，将它们标记为False
# 使用埃拉托斯特尼筛法，遍历从2到根号n的所有数字
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:# 如果当前数字为质数
# 将所有当前质数的倍数标记为非质数
for j in range(i*i, n, i):
is_prime[j] = False
# 统计is_prime中值为True的个数，即质数的个数
count = sum(is_prime)
return count
法三、线性筛法
- 埃氏筛的优化，埃氏筛同一个数比如12=26/34会被划多次造成浪费，线性筛则对此优化，
class Solution:
def countPrimes(self, n: int) -> int:
if n <= 2:
return 0
is_prime = [True] * n # 初始化一个布尔数组，用于标记数字是否为质数
primes = [] # 创建一个空列表，用于存储质数
for i in range(2, n):# 遍历从2到n的所有数字
if is_prime[i]:# 如果当前数字为质数，将其添加到质数列表
primes.append(i)
for p in primes: # 遍历质数列表
if p * i >= n: # 计算当前质数与当前数字的乘积
break # 如果乘积大于n，跳出循环
is_prime[p * i] = False # 将乘积标记为非质数
if i % p == 0:# 如果当前数字能被当前质数整除，跳出内层循环
break
return len(primes)