Go语言中Sieve算法的数组越界与整数溢出问题解析

package main

func main() {
    limit := 46349 // 当 limit 达到 46350 时，问题更明显
    sieved_numbers := make([]bool, limit)
    var j = 0
    var i = 2

    for ; i < limit; i++ {
        if !sieved_numbers[i] {
            // 核心问题发生在此处：j = i * i
            for j = i * i; j < limit; j += i {
                sieved_numbers[j] = true
            }
        }
    }
}

package main

func main() {
    limit := 100000 // 尝试更大的 limit
    sieved_numbers := make([]bool, limit)
    var i = 2

    for ; i < limit; i++ {
        if !sieved_numbers[i] {
            // 将 j 声明为 int64，或者在计算时进行类型转换
            // 这里为了简洁，直接将 i * i 的结果赋给 int64 类型的 j
            for j_val := int64(i) * int64(i); j_val < int64(limit); j_val += int64(i) {
                // 在访问切片前，确保 j_val 在 int 范围内且非负
                // 如果 limit 超过 int 的最大值，这里还需要额外的处理
                if j_val >= 0 && j_val < int64(len(sieved_numbers)) {
                    sieved_numbers[j_val] = true
                } else {
                    // 如果 j_val 超出了切片索引范围，说明 i*i 已经太大，
                    // 后续的 j_val + i 也会超出，可以直接跳出内层循环
                    break
                }
            }
        }
    }
}

package main

func main() {
    limit := 100000
    sieved_numbers := make([]bool, limit)
    var i = 2

    for ; i < limit; i++ {
        if !sieved_numbers[i] {
            // 提前检查，避免 i * i 溢出
            // 如果 i * i 会溢出，或者 i * i 已经大于等于 limit，则跳过内层循环
            // 这里使用 int64(i) * int64(i) 来安全地计算平方
            if int64(i)*int64(i) >= int64(limit) {
                continue
            }

            // 确保 j 从一个非负且在 limit 范围内的值开始
            // 此时 j 的类型可以保持为 int，因为 i*i 已经检查过不会溢出且在 limit 范围内
            for j := i * i; j < limit; j += i {
                sieved_numbers[j] = true
            }
        }
    }
}

// 检查 i*i 是否会溢出 int 类型，或者是否会超出 limit
// 对于 int 类型，如果 i > sqrt(MaxInt)，则 i*i 会溢出
// MaxInt32 = 2147483647, sqrt(MaxInt32) approx 46340
// MaxInt64 = 9223372036854775807, sqrt(MaxInt64) approx 3037000000
const MaxInt = int(^uint(0) >> 1) // 获取当前平台 int 的最大值

// 在循环内部
if !sieved_numbers[i] {
    // 检查 i*i 是否会溢出 Go 的 int 类型
    // 另一种检查方式是 if i > MaxInt/i (如果 i != 0)
    // 但对于 i*i 的情况，直接转换为 int64 计算并比较更安全
    if int64(i)*int64(i) >= int64(limit) {
        continue // i*i 已经超出 limit，无需继续筛选
    }

    // 此时 j = i * i 保证在 int 范围内且小于 limit
    for j := i * i; j < limit; j += i {
        sieved_numbers[j] = true
    }
}