Go语言中高效并发素数生成器的实现与优化

package main

import (
    "fmt"
    "math"
    "sync"
    "time"
)

// isPrime 检查一个数字是否为素数，采用试除法并优化至平方根。
// 复杂度近似 O(sqrt(n))。
func isPrime(n int) bool {
    if n < 2 {
        return false
    }
    if n == 2 || n == 3 {
        return true
    }
    if n%2 == 0 || n%3 == 0 { // 排除偶数和3的倍数
        return false
    }
    // 只需要检查到数字的平方根
    limit := int(math.Sqrt(float64(n)))
    // 检查形如 6k ± 1 的因子
    for i := 5; i <= limit; i += 6 {
        if n%i == 0 || n%(i+2) == 0 {
            return false
        }
    }
    return true
}

// generateNumbers 将指定范围内的数字发送到通道。
func generateNumbers(start, end int, out chan<- int) {
    defer close(out) // 所有数字发送完毕后关闭通道
    for i := start; i <= end; i++ {
        out <- i
    }
}

// worker 从输入通道接收数字，判断是否为素数，并将素数发送到输出通道。
func worker(id int, in <-chan int, out chan<- int, wg *sync.WaitGroup) {
    defer wg.Done() // 工作完成后通知 WaitGroup
    for num := range in {
        if isPrime(num) {
            out <- num
        }
    }
}

func main() {
    const limit = 1000000 // 查找素数的上限
    const numWorkers = 8  // 并发工作者数量，通常设为CPU核心数或其倍数

    // nums 通道：用于发送待检查的数字给工作者
    nums := make(chan int, 1000)
    // primes 通道：用于从工作者接收发现的素数
    primes := make(chan int, 1000)

    var wg sync.WaitGroup // 用于等待所有工作者完成

    start := time.Now() // 记录开始时间

    // 1. 启动一个 Goroutine 生成待检查的数字
    // 从2开始，因为2是最小的素数
    go generateNumbers(2, limit, nums)

    // 2. 启动多个 worker Goroutine
    wg.Add(numWorkers) // 增加 WaitGroup 计数器
    for i := 0; i < numWorkers; i++ {
        go worker(i, nums, primes, &wg)
    }

    // 3. 启动一个 Goroutine，等待所有 worker 完成后关闭 primes 通道
    // 这样主 Goroutine 在 range primes 时知道何时结束
    go func() {
        wg.Wait()       // 等待所有 worker Goroutine 完成
        close(primes)   // 关闭 primes 通道
    }()

    // 4. 主 Goroutine 收集并打印素数
    foundPrimes := []int{}
    for p := range primes {
        foundPrimes = append(foundPrimes, p)
    }

    elapsed := time.Since(start) // 计算总耗时

    fmt.Printf("在 %d 内找到了 %d 个素数，耗时 %s\n", limit, len(foundPrimes), elapsed)
    // fmt.Println("素数列表 (部分显示):", foundPrimes[:min(len(foundPrimes), 20)]) // 可选：打印部分素数
}

// 辅助函数，用于打印部分素数时避免索引越界
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}