分段筛法实现与边界错误修复详解

本文深入解析了Go语言中分段埃氏筛法在解决SPOJ经典题PRIME1时的关键实现细节，直击初学者极易忽略的边界错误——尤其是循环索引范围与数组长度不匹配导致的素数遗漏问题（如区间[3,5]中漏判5），并通过修正前后的代码对比，清晰揭示了“j

本文详解 SPOJ 经典题 PRIME1 的 Go 语言实现，重点剖析分段埃氏筛（Segmented Sieve）的正确逻辑、常见边界漏洞（如数组越界与漏判），并通过对比修正前后代码，揭示 j <= n-m 这一关键循环条件修正如何解决“输出少一行”的 Wrong Answer 根源。

本文详解 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 < 2 ⇒ j=0,1），j=2（对应 3+2=5）未被检查，故 5 被遗漏 → 输出仅 3，缺失 5，与题目要求不符。

✅ 正确写法必须覆盖全部 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 的分段筛实现，逻辑框架易懂，但边界条件极易出错。务必确保：

1. 区间数组长度 = n − m + 1；
2. 遍历索引覆盖 0 至 n−m（含）；
3. 显式跳过 ≤ 1 的数；
4. 小素数标记起点严格 ≥ max(p², m)。

一次看似微小的 < 与 <= 差异，便是 WA 与 AC 的分水岭——算法工程中，鲁棒性始于对每一个下标的敬畏。

理论要掌握，实操不能落！以上关于《分段筛法实现与边界错误修复详解》的详细介绍，大家都掌握了吧！如果想要继续提升自己的能力，那么就来关注golang学习网公众号吧！