Go语言素数生成教程：Atkin筛法详解与实现

package main

import (
    "fmt"
    "math"
)

// N 定义了生成素数的上限
const N = 100

func main() {
    var x, y, n int
    // 计算N的平方根，用于优化循环边界
    nsqrt := math.Sqrt(N)

    // is_prime 数组用于标记每个数是否为素数。
    // is_prime[i] 为 true 表示 i 是素数，false 表示 i 是合数或未确定。
    // 数组大小为 N+1，以便索引与数值对应 (0到N)。
    is_prime := make([]bool, N+1)

    // 第一阶段：根据Atkin筛法的三个二次型公式预筛选素数
    // 遍历 x 和 y 从 1 到 sqrt(N) 的所有组合
    for x = 1; float64(x) <= nsqrt; x++ {
        for y = 1; float64(y) <= nsqrt; y++ {
            // 公式1: n = 4x^2 + y^2
            // 如果 n <= N 且 n % 12 等于 1 或 5，则翻转 is_prime[n] 的标记
            n = 4*(x*x) + y*y
            if n <= N && (n%12 == 1 || n%12 == 5) {
                is_prime[n] = !is_prime[n]
            }

            // 公式2: n = 3x^2 + y^2
            // 如果 n <= N 且 n % 12 等于 7，则翻转 is_prime[n] 的标记
            n = 3*(x*x) + y*y
            if n <= N && n%12 == 7 {
                is_prime[n] = !is_prime[n]
            }

            // 公式3: n = 3x^2 - y^2
            // 注意：此公式要求 x 必须大于 y
            // 如果 n <= N 且 n % 12 等于 11，则翻转 is_prime[n] 的标记
            n = 3*(x*x) - y*y
            if x > y && n <= N && n%12 == 11 {
                is_prime[n] = !is_prime[n]
            }
        }
    }

    // 第二阶段：去除合数的倍数
    // 遍历所有可能的素数 n (从 5 开始，因为 2 和 3 会单独处理)
    // 如果 n 被标记为素数，则将其平方 n*n 及其所有倍数标记为合数
    for n = 5; float64(n) <= nsqrt; n++ {
        if is_prime[n] { // 如果 n 在第一阶段被标记为素数候选
            // 将 n 的平方及其倍数标记为合数
            // 这里的优化是只从 n*n 开始，因为小于 n*n 的倍数已经在前面被更小的素数处理过了
            for y = n * n; y <= N; y += n * n {
                is_prime[y] = false
            }
        }
    }

    // 第三阶段：处理特殊素数2和3
    // Atkin筛法的设计不直接处理素数2和3，需要手动设置
    if N >= 2 {
        is_prime[2] = true
    }
    if N >= 3 {
        is_prime[3] = true
    }

    // 第四阶段：收集所有被标记为素数的数字
    primes := make([]int, 0) // 动态切片存储素数
    for i := 0; i <= N; i++ { // 遍历整个标记数组
        if is_prime[i] {
            primes = append(primes, i)
        }
    }

    // 打印结果
    fmt.Printf("小于等于 %d 的所有素数是:\n", N)
    for _, p := range primes {
        fmt.Println(p)
    }
}