1. 算法原理：从O(N^2)到O(N^1.5)的优化
在生成素数时，一种常见的简单方法是对每个待检测的数字m进行试除，判断其是否能被小于m的任何数整除。这种方法的复杂度接近o(n^2)，因为它需要对每个数字进行多次除法运算。例如，要判断一个数m是否为素数，最直观的方法是尝试用从2到m-1的所有整数去除它。
然而，一个关键的数学优化是：如果一个数m不是素数，它必然有一个小于或等于其平方根的因子。这意味着，我们只需要检查从2到sqrt(m)范围内的数是否能整除m即可。如果在这个范围内找不到任何因子，那么m就是素数。通过这种优化，将单个素数判断的复杂度从O(N)降低到O(sqrt(N))。当我们需要生成一系列素数时，整体复杂度会从大约O(N^2)降低到O(N^1.5)（或更精确地说是O(N * sqrt(N))）。
这种优化对于并发素数生成尤为重要，因为它减少了每个独立素数判断任务的工作量，从而使并发处理的收益更加显著。
2. Go语言并发实现
Go语言的并发模型，基于Goroutine和Channel，非常适合实现这种并行化的素数生成器。我们可以将待检测的数字流式地发送到一个通道，然后启动多个Goroutine作为“工人”，每个工人从通道中接收数字并独立地执行素数判断（应用O(N^1.5)优化），最后将找到的素数发送到另一个通道。
核心思想如下：
立即学习“go语言免费学习笔记（深入）”；
- 生产者 (Producer)：一个Goroutine负责生成从2到指定上限的所有整数，并将它们发送到一个输入通道。
- 消费者/工人 (Workers)：多个Goroutine从输入通道接收数字。每个Goroutine内部调用一个优化过的isPrime函数来判断数字是否为素数。如果是素数，则将其发送到一个输出通道。
- 收集器 (Collector)：一个Goroutine从输出通道接收所有素数，并将它们收集到一个列表中。
- 同步机制：使用sync.WaitGroup来确保所有工人Goroutine都完成了它们的任务，并且所有素数都已被收集，然后才能关闭通道并返回结果。
3. 示例代码
以下是一个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)
}
}
4. 注意事项
- worker数量：numWorkers的数量应根据系统的CPU核心数进行调整。通常设置为runtime.NumCPU()或其倍数，以充分利用CPU资源，避免过多的Goroutine切换开销。
- 通道缓冲区：nums和primes通道的缓冲区大小（示例中为100）会影响性能。适当的缓冲区大小可以减少Goroutine之间的阻塞，提高数据流动的效率。如果缓冲区过小，可能导致生产者或消费者频繁阻塞；如果过大，则可能消耗更多内存。
- 素数顺序：由于素数是并发收集的，最终结果列表的顺序可能不是递增的。因此，在返回结果前，需要对foundPrimes切片进行排序，以确保素数列表的有序性。
- 内存消耗：对于非常大的limit值，foundPrimes切片可能会存储大量的素数，从而消耗大量内存。如果只需要处理素数而不必一次性存储所有素数，可以考虑在收集器Goroutine中直接处理（例如，打印、写入文件或进行其他计算），而不是全部存入内存。
- 与经典筛法的对比：本教程侧重于优化并发的试除法素数生成。对于生成大量素数，经典的“埃拉托斯特尼筛法”（Sieve of Eratosthenes）在理论复杂度上通常更优（接近O(N log log N)），但其并发化实现通常更为复杂，且不直接适用sqrt(m)这种针对单个数的优化。本方法更适用于需要并发处理每个数字的素性测试场景。
5. 总结
通过将单个素数判断的试除法从O(N)优化到O(sqrt(N))，并结合Go语言强大的并发原语Goroutine和Channel，我们能够构建一个高效且可扩展的并发素数生成器。这种模式不仅适用于素数生成，也可以推广到其他需要并行处理大量独立任务的场景。理解并应用这种优化和并发模式，将有助于开发者在Go语言中编写出性能更优异、响应更快的应用程序。
