Go语言中高效并发素数生成：利用平方根优化提升效率

package main

import (
    "fmt"
    "sort"
    "sync"
)

// isPrime 检查一个数是否为素数，使用O(sqrt(n))优化
// 对于偶数和3的倍数进行快速排除，进一步优化循环步长
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
    }
    // 从5开始，步长为6检查（跳过所有2和3的倍数）
    // 例如：5, 7, 11, 13, 17, 19...
    for i := 5; i*i <= n; i += 6 {
        if n%i == 0 || n%(i+2) == 0 {
            return false
        }
    }
    return true
}

// primeWorker Goroutine从in通道接收数字，判断素数后发送到out通道
func primeWorker(in <-chan int, out chan<- int, wg *sync.WaitGroup) {
    defer wg.Done() // Goroutine结束时通知WaitGroup
    for n := range in {
        if isPrime(n) {
            out <- n
        }
    }
}

// GeneratePrimes 并发生成指定范围内的素数
// limit: 生成素数的上限
// numWorkers: 启动的worker Goroutine数量
func GeneratePrimes(limit int, numWorkers int) []int {
    nums := make(chan int, 100)    // 用于发送待检测数字的通道，带缓冲
    primes := make(chan int, 100) // 用于接收素数的通道，带缓冲
    var wg sync.WaitGroup          // 用于等待所有worker完成

    // 启动worker goroutines
    for i := 0; i < numWorkers; i++ {
        wg.Add(1) // 增加WaitGroup计数
        go primeWorker(nums, primes, &wg)
    }

    // 生产者：将数字发送到nums通道
    go func() {
        for i := 2; i <= limit; i++ {
            nums <- i
        }
        close(nums) // 发送完毕，关闭nums通道，通知worker不再有新任务
    }()

    // 消费者：收集素数
    var foundPrimes []int
    var collectWg sync.WaitGroup // 用于等待素数收集完成
    collectWg.Add(1)
    go func() {
        defer collectWg.Done()
        for p := range primes { // 从primes通道接收素数，直到通道关闭
            foundPrimes = append(foundPrimes, p)
        }
    }()

    // 等待所有worker完成
    wg.Wait()
    close(primes) // 所有worker都已完成，关闭primes通道，通知收集器不再有新素数

    // 等待消费者完成素数收集
    collectWg.Wait()

    // 对收集到的素数进行排序（并发收集可能导致乱序）
    sort.Ints(foundPrimes)
    return foundPrimes
}

func main() {
    limit := 1000000 // 生成100万以内的素数
    numWorkers := 4  // 根据CPU核心数调整，通常设置为GOMAXPROCS或其倍数
    fmt.Printf("生成 %d 以内的素数，使用 %d 个worker...\n", limit, numWorkers)

    primes := GeneratePrimes(limit, numWorkers)

    fmt.Printf("找到 %d 个素数。\n", len(primes))
    // 打印前10个素数，验证结果
    if len(primes) > 10 {
        fmt.Println("前10个素数:", primes[:10])
    } else {
        fmt.Println("所有素数:", primes)
    }
}