核心概述
埃拉托斯特尼筛（Sieve of Eratosthenes）：在区间 [2..n] 线性空间内筛出全部质数，经典复杂度 O(n log log n)，可配合位集降内存；超大区间可用分段筛。
原文引述
Description: Classic sieve to mark all primes up to n. Supports bitset memory optimization and segmented variant for large ranges. Time: O(n log log n); Memory: O(n) bits with bitset
展开阐述
-
函数/接口（据实现）
- sieve(n) → primes, isPrime：返回质数列表 primes 及布尔数组/位集 isPrime。
- 可选：segmentedSieve(L, R) → 返回区间 [L, R] 内的质数（需预筛到 √R）。
- 注：最小质因子 spf/线性筛属085-数论-快速筛的范畴。
-
核心算法（标记合数）
- 初始化：isPrime[0]=isPrime[1]=false，2..n 初设为 true；primes 为空。
- 对 i from 2..⌊√n⌋：
- 若 isPrime[i] 为 true，则从 j=i·i 开始步长 i 标记合数：for j=i*i; j≤n; j+=i: isPrime[j]=false。
- 扫描 2..n，将 isPrime[i]==true 的 i 加入 primes。
- 位集优化：用 bitset/压缩奇数（仅存奇数位）可将内存近乎减半。
-
分段筛（大范围）
- 先普通筛得到小质数表 P（到 √R）。
- 在目标块 [L,R] 建局部标记数组，初值均为 true；对每个 p∈P：
- 从 s = ceil(L/p)*p 开始，按步长 p 标记到 R（若 s==p 且 p≥L，则从 s+p 开始以避免将 p 自身标为合数）。
- 块内未标记者即为质数；按块滚动可覆盖超大范围。
-
输出语义
- primes：升序的全部质数。
- isPrime[i]：表示 i 是否为质数（若采用奇数压缩，仅对映射索引有效）。
-
复杂度
- 经典筛 O(n log log n)；空间 O(n)（位集为 O(n) 位）。
- 分段筛时间近似相当，空间降为 O(块大小)。
-
使用与注意
- 循环上界使用 ii ≤ n，需用 64 位防止 ii 溢出；或写 j=(long long)i*i。
- 标记起点从 i*i 而非 2i，可避免重复标记（因 i<j 的较小质因子已处理）。
- 分段筛需处理 L=1 的边界（1 非质数）；以及 L==0/负值的规整。
- 若需求分解/φ/μ 等，请参见085-数论-快速筛（维护 spf/phi/mu）与084-数论-因数分解。