本文详解 SPOJ 经典题 PRIME1 的 Go 语言实现，重点剖析分段埃氏筛（Segmented Sieve）的正确逻辑、常见边界漏洞（如数组越界与漏判），并通过对比修正前后代码，揭示 j
本文详解 spoj 经典题 prime1 的 go 语言实现，重点剖析分段埃氏筛（segmented sieve）的正确逻辑、常见边界漏洞（如数组越界与漏判），并通过对比修正前后代码，揭示 `j
SPOJ PRIME1 要求在多个区间 [m, n]（其中 n ≤ 10⁹，但区间长度 n−m ≤ 10⁵）内高效输出所有素数。由于 n 可达 10 亿，无法直接筛出全部素数；而区间长度有限，分段筛法（Segmented Sieve） 是最优解：先用普通埃氏筛预处理 √n_max 以内的所有素数（本例中 n_max ≤ 10⁹ ⇒ √n_max ≤ 31623），再用这些小素数去标记每个查询区间的合数。
核心思想是为每个测试用例 [m, n] 分配一个长度为 len = n − m + 1 的布尔切片 isComposite[i]，初始全为 false；对每个预筛出的小素数 p，从 max(p², ⌈m/p⌉ × p) 开始，以步长 p 标记其在 [m, n] 内的所有倍数为 true。最终，所有 isComposite[j] == false 且对应数值 m + j > 1 的数即为素数。
然而，原始代码存在一个致命边界错误：
// ❌ 错误写法：循环上界遗漏最后一个索引
for j = 0; j < case_n[i]-case_m[i]; j++ { // 索引范围：0 ~ (n−m−1)，共 n−m 个元素
if !EratosthenesArray[i][j] {
ret := case_m[i] + j
if ret > 1 {
fmt.Println(ret)
}
}
}该循环仅遍历了 n − m 个索引（0 到 n−m−1），但数组长度实际为 n − m + 1（索引 0 到 n−m）。因此，最大值 n 对应的索引 n−m 被完全跳过，导致每个区间恒漏输出 n（若 n 是素数）——这正是样例中 1 10 输出缺少 7？不，实测发现 7 存在，但 10 本身非素数；真正影响的是当 n 恰为素数时（如 3 5 中的 5），j 最大只到 1（因 5−3=2，j
✅ 正确写法必须覆盖全部 n−m+1 个位置：
// ✅ 正确写法：使用 <= 确保包含末位索引
for j = 0; j <= case_n[i]-case_m[i]; j++ { // 索引范围：0 ~ (n−m)，共 n−m+1 个元素
if !EratosthenesArray[i][j] {
ret := case_m[i] + j
if ret > 1 {
fmt.Println(ret)
}
}
}此外，还需注意以下关键细节：
- 1 不是素数：筛选后需显式排除 ret ≤ 1（尤其当 m = 1 时，j = 0 对应 1，必须跳过）；
-
起始标记点计算要严谨：对素数 p，首个需标记的倍数是 ≥ m 的最小 p 的倍数，即 start = max(p*p, ceil(m/p)*p)；原始代码中 start := (case_m[kase] - i*i) / i 在负数除法时行为未定义（Go 中为向零取整），更安全写法是：
start := case_m[kase] / i if case_m[kase]%i != 0 { start++ } start = max(start, i*i) // 确保不小于 p² - 内存与性能优化：使用 map[int64][]bool 存储各区间状态虽可行，但 []bool 底层仍占 1 byte/element；可改用 []byte 或位图进一步压缩（本题非必需）；预筛上限 √n_max 仅约 31623，筛表内存可忽略。
总结：PRIME1 的分段筛实现，逻辑框架易懂，但边界条件极易出错。务必确保：
- 区间数组长度 = n − m + 1；
- 遍历索引覆盖 0 至 n−m（含）；
- 显式跳过 ≤ 1 的数；
- 小素数标记起点严格 ≥ max(p², m)。
一次看似微小的
