引言：并发素数生成器的挑战与优化方向
在并发编程中，素数生成是一个经典的案例，常用于演示并发模型的优雅性。然而，一个常见的并发素数生成器（例如基于通道的流水线筛法）虽然结构精巧，但在处理大量数字时可能会面临效率问题。原始的“朴素”素数判断方法（即检查一个数m是否能被所有小于m的数整除）其时间复杂度接近O(n^2)。当我们将这种逻辑并发化时，虽然能利用多核优势，但算法本身的低效性依然存在。
为了提升效率，一种常见的优化思路是将素数判断的复杂度降低到O(n^1.5)，即对于一个数字m，我们只需要检查它能否被小于或等于其平方根的数整除。这是因为如果一个合数m有一个大于其平方根的因子a，那么它必然还有一个小于或等于其平方根的因子b（m = a * b）。因此，我们只需检查到平方根即可。将这种优化应用到并发素数生成器中，需要精心设计并发结构。
基于试除法优化的并发素数生成器设计
我们选择采用基于试除法的并发素数生成方案，该方案能够直接应用平方根优化。其核心思想是：
- 数字生成器： 一个Goroutine负责生成待检查的数字序列。
- 并发工作池： 多个Goroutine作为工作者，从数字生成器接收数字，并独立地进行素数判断。
- 素数收集器： 另一个Goroutine负责收集所有工作者发现的素数。
Go语言的Goroutine和Channel机制非常适合实现这种生产者-消费者模型。
立即学习“go语言免费学习笔记（深入）”；
核心素数判断函数
首先，我们实现一个高效的isPrime函数，它利用了平方根优化以及一些基本的素数性质（如跳过偶数和3的倍数）。
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 函数： 负责将从start到end的数字发送到输出通道。
- worker 函数： 接收输入通道的数字，调用isPrime进行判断，如果是素数则发送到输出通道。sync.WaitGroup用于协调所有工作者的完成。
- main 函数： 协调整个流程，启动数字生成器、多个工作者，并收集素数。
// 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
}注意事项与性能考量
- 通道缓冲大小： nums 和 primes 通道的缓冲大小 (1000) 需要根据实际情况调整。适当的缓冲可以减少 Goroutine 之间的阻塞，提高吞吐量，但过大的缓冲会增加内存消耗。
- 工作者数量： numWorkers 的最佳值通常取决于系统的CPU核心数。对于CPU密集型任务，将其设置为 runtime.NumCPU() 或其倍数（例如 runtime.NumCPU() * 2）是一个好的起点，然后根据实际测试进行微调。
- 任务粒度： 这种并发模型适用于素数判断这种CPU密集型任务。每个数字的判断是独立的，可以并行执行。
- 与Sieve of Eratosthenes的对比： 本文实现的方案是基于试除法的并发素数生成器，其单个数判断效率为O(sqrt(n))。而传统的Sieve of Eratosthenes（埃拉托斯特尼筛法）在查找给定上限内的所有素数时，通常具有更好的整体时间复杂度（接近O(N log log N)），尤其是在单机串行执行时。然而，埃拉托斯特尼筛法的并发化通常更为复杂，因为它涉及共享状态（标记数组）的同步问题。本文的方案避免了复杂的共享状态，通过独立计算来达到并发。
- 内存消耗： 收集所有素数到切片 foundPrimes 会消耗大量内存，特别是当 limit 非常大时。如果只需要处理或流式输出素数，可以省略这一步，直接在 for p := range primes 循环中进行处理。
总结
通过将素数判断的核心算法从O(n)优化到O(sqrt(n))，并结合Go语言强大的并发原语（Goroutine和Channel），我们成功实现了一个高效且结构清晰的并发素数生成器。这种设计模式不仅适用于素数生成，也可以推广到其他需要并行处理独立计算任务的场景。在选择素数生成算法时，应根据具体需求（如生成范围、是否需要所有素数、并发度要求等）权衡试除法与筛法的优劣。对于需要并发生成大量素数且每个数字判断相对独立的场景，本文的并发试除法是一个非常有效的解决方案。
