[Leetcode 204] 质数计数

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定整数 n ,返回 所有小于非负整数 n 的质数的数量 。
示例 1:
示例 2:
示例 3:
 

解法一:试除更小的质数

合数一定有至少一个质因子
与其拿 i 去除所有更小的整数,不如只除更小的质数;
并且只需要除到 √i 为止(i 若有因子,必有一个 ≤ √i)。
从 2 开始,一个个试:判断 i 是否能被“之前已经找到的质数”整除;若都不能整除,i 就是新质数。
复杂度
  • 时间:平均远好于朴素 O(n√n),但严格上界仍可到 O(n√n)
  • 空间:O(π(n))(存质数列表,π(n) 是质数个数)。

解法二:埃氏筛

“合数 = 有质因子 × 另一个整数”。只要遇到一个质数,就能一次性批量剔除它的倍数,比对每个数逐一试除要高效得多。
维护一个布尔数组 is_prime[0..n],初始都当作“可能是质数”。遇到质数 i,就把它的所有倍数标记为合数。
关键优化:
  1. 只筛到 i*i <= n:超过 √n 的质数,其最小未标记倍数至少是 i*i,但 i*i > n 时无需再筛。
  1. i*i 开始标记2*i, 3*i, ..., (i-1)*i 早就被更小的素因子标记过了,避免重复工作。
复杂度
  • 时间:O(n log log n)(经典结论,极接近线性)。
  • 空间:O(n)

解法三:线性筛(欧拉筛)

埃氏筛会“重复标记”某些合数(被多个质因子轮番扫到)。
线性筛通过“按质数列表驱动 + 遇到能整除就 break”,确保每个合数仅被它的最小质因子标记一次,从而把总操作数控制在线性级别。
复杂度
  • 时间:O(n)
  • 空间:O(n)

解法四:分段筛(Segmented Sieve)

埃氏筛的内存瓶颈是 O(n) 的布尔数组。
n 很大、内存有限,无法开 O(n) 数组时(例如区间质数统计、离线大数据处理),
可以用分段筛把范围切成多个“可放入内存的小块”,每块用同一批小质数进行局部筛除,内存开销变为 O(B + √n)
具体步骤:
  1. 先把 [2, √n] 的质数用普通埃氏筛求出来;
  1. 然后按块(如每块长度 B)处理区间 [L, R],用这些小质数去标记当前块里的合数;
  1. 块内剩下没被标记的就是该段内的质数。
复杂度
  • 时间:与埃氏筛同阶,O(n log log n)
  • 空间:O(√n + B),其中 B 是块大小(可调)。
Buy Me a Coffee
上一篇
[Leetcode 200] 岛屿数量
下一篇
[Leetcode 206] 反转链表