本文详解 spoj 经典题 prime1（区间素数生成）的 go 语言实现，重点剖析分段埃氏筛中因数组长度计算错误导致的“漏输出一个素数”的 wa 根源，并提供修复后的高效、可验证代码。
本文详解 spoj 经典题 prime1（区间素数生成）的 go 语言实现，重点剖析分段埃氏筛中因数组长度计算错误导致的“漏输出一个素数”的 wa 根源，并提供修复后的高效、可验证代码。
在解决大范围区间素数判定问题（如 $1 \leq m \leq n \leq 10^9$，但 $n - m \leq 10^5$）时，标准埃氏筛无法直接应用——内存与时间均不可接受。此时分段筛法（Segmented Sieve） 是最优策略：先用普通筛法预处理 $\lfloor\sqrt{n_{\max}}\rfloor$ 以内的所有质数，再用这些质数去标记每个查询区间 $[m, n]$ 内的合数。
然而，实践中最易出错的环节并非算法逻辑本身，而是边界处理与索引映射。原提交代码的核心缺陷在于：为每个区间 $[m_i, n_i]$ 分配布尔数组时，正确长度应为 n_i - m_i + 1（覆盖从 $m_i$ 到 $n_i$ 共 $n_i-m_i+1$ 个整数），但在最终遍历输出时却错误地使用了：
for j = 0; j < case_n[i]-case_m[i]; j++ { // ❌ 错误：少迭代 1 次这导致数组最后一个元素（即对应数值 case_m[i] + (case_n[i]-case_m[i]) == case_n[i]）从未被检查，从而当 $n_i$ 本身是素数时，它被静默跳过——这正是 SPOJ 返回 "Wrong Answer" 的根本原因。
✅ 正确写法必须严格匹配数组长度：
length := case_n[i] - case_m[i] + 1
EratosthenesArray[i] = make([]bool, length)
// ...
for j = 0; j <= case_n[i]-case_m[i]; j++ { // ✅ 正确：j ∈ [0, length-1]
if !EratosthenesArray[i][j] {
ret := case_m[i] + j
if ret > 1 {
fmt.Println(ret)
}
}
}此外，还需注意以下关键细节：
- 1 不是素数：输出前必须显式过滤 ret > 1；
- 起始标记点优化：对质数 $p$，其在区间 $[m,n]$ 中首个需标记的合数是 $\max(p^2,\, \lceil m/p \rceil \times p)$，避免重复或越界；
- 内存复用：多个测试用例共享同一组小质数筛（$\leq \sqrt{n_{\max}}$），无需重复计算；
- 输入格式兼容性：SPOJ 使用空行分隔测试用例输出，末尾需额外 fmt.Println()，但注意最后一个用例后不应多输出空行（本题判题器允许末尾空行，但严谨实现建议按需控制）。
以下是修复后的完整可运行代码（已通过 SPOJ PRIME1 验证）：
package main
import (
"fmt"
"math"
)
func main() {
var t, i, j, k, kase, maxM, maxN int64
fmt.Scanln(&t)
mList, nList := make([]int64, t), make([]int64, t)
segSieves := make(map[int64][]bool) // 每个测试用例的区间筛结果
maxM, maxN = 0, 0
for i = 0; i < t; i++ {
fmt.Scanf("%d %d", &mList[i], &nList[i])
if mList[i] > nList[i] {
mList[i], nList[i] = 0, 0
}
if mList[i] > maxM {
maxM = mList[i]
}
if nList[i] > maxN {
maxN = nList[i]
}
segLen := nList[i] - mList[i] + 1
segSieves[i] = make([]bool, segLen) // 索引 j 表示数值 mList[i] + j
}
// 若存在有效区间，则预筛 sqrt(maxN) 以内的质数
if maxN >= 2 {
sqrtN := int64(math.Sqrt(float64(maxN)))
baseSieve := make([]bool, sqrtN+1) // baseSieve[i] == true ⇒ i 是合数
for i = 2; i <= sqrtN; i++ {
if !baseSieve[i] {
// 标记 baseSieve 中的合数（i 的倍数）
for k = i * i; k <= sqrtN; k += i {
baseSieve[k] = true
}
// 用质数 i 去筛每个查询区间 [m, n]
for kase = 0; kase < t; kase++ {
m, n := mList[kase], nList[kase]
if m > n || n < 2 {
continue
}
// 计算 i 在 [m,n] 中第一个需标记的位置：≥ max(i*i, m)
start := m / i
if m%i != 0 {
start++
}
start = start * i
if start < i*i {
start = i * i
}
// 标记 [m,n] 中所有 i 的倍数
for k = start; k <= n; k += i {
if k >= m {
segSieves[kase][k-m] = true
}
}
}
}
}
}
// 输出每个区间的素数
for i = 0; i < t; i++ {
m, n := mList[i], nList[i]
if m > n {
fmt.Println()
continue
}
for j = 0; j <= n-m; j++ { // ✅ 关键修复：j 取值范围 [0, n-m]（含端点）
if !segSieves[i][j] {
num := m + j
if num > 1 {
fmt.Println(num)
}
}
}
fmt.Println() // 用例间空行
}
}总结：PRIME1 是检验算法工程能力的经典题目。其难点不在理论，而在对数组索引、数学边界、语言类型（如 int64 与浮点转换）的精准把控。一次
