本文详解 spoj 经典题 prime1（区间素数生成）的 go 语言实现，重点剖析分段埃氏筛中因数组长度计算错误导致的“漏输出一个素数”的 wa 根源，并提供修复后的高效、可验证代码。
本文详解 spoj 经典题 prime1（区间素数生成）的 go 语言实现，重点剖析分段埃氏筛中因数组长度计算错误导致的“漏输出一个素数”的 wa 根源，并提供修复后的高效、可验证代码。
在解决大范围区间素数判定问题（如 $1 leq m leq n leq 10^9$，但 $n – m leq 10^5$）时，标准埃氏筛无法直接应用——内存与时间均不可接受。此时分段筛法（Segmented Sieve） 是最优策略：先用普通筛法预处理 $lfloorsqrt{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 与浮点转换）的精准把控。一次