Atkin筛法是一种现代高效的素数筛选算法，时间复杂度为O(N/log log N)，相比传统的埃拉托斯特尼筛法在处理大范围数值时性能更优。它的核心思路是通过特定的二次型同余条件筛选出可能的素数候选，再经过标记排除得到最终的素数集合，适合需要生成大量素数的场景。
Atkin筛法核心原理
Atkin筛法的筛选逻辑基于以下三个二次型同余规则，满足任意一条的正整数n如果是平方数则排除，否则标记为候选素数：
- 当n mod 12 = 1、5时，若n = 4x² + y²有奇数个正整数解，则标记n
- 当n mod 12 = 7时，若n = 3x² + y²有奇数个正整数解，则标记n
- 当n mod 12 = 11时，若n = 3x² - y²（x > y）有奇数个正整数解，则标记n
完成初步标记后，需要遍历所有小于等于sqrt(N)的候选素数，将其倍数全部标记为合数，最终剩余的标记数就是所有小于等于N的素数。
Go语言实现Atkin筛法
下面是基于Go语言实现的Atkin筛法完整代码，可生成小于等于指定上限的所有素数：
package main
import (
"fmt"
"math"
)
// atkinSieve 生成小于等于limit的所有素数
func atkinSieve(limit int) []int {
if limit < 2 {
return []int{}
}
// 初始化标记数组，默认都是合数
isPrime := make([]bool, limit+1)
isPrime[2] = true
isPrime[3] = true
// 计算x和y的上限
xLimit := int(math.Sqrt(float64(limit)))
for x := 1; x <= xLimit; x++ {
xSquare := x * x
yLimit := int(math.Sqrt(float64(limit - 4*xSquare)))
if yLimit < 1 {
yLimit = 1
}
for y := 1; y <= yLimit; y++ {
ySquare := y * y
n := 4*xSquare + ySquare
if n <= limit && (n%12 == 1 || n%12 == 5) {
isPrime[n] = !isPrime[n]
}
n = 3*xSquare + ySquare
if n <= limit && n%12 == 7 {
isPrime[n] = !isPrime[n]
}
if x > y {
n = 3*xSquare - ySquare
if n <= limit && n%12 == 11 {
isPrime[n] = !isPrime[n]
}
}
}
}
// 排除平方数并标记合数倍数
rLimit := int(math.Sqrt(float64(limit)))
for r := 5; r <= rLimit; r++ {
if isPrime[r] {
// 标记r的平方的倍数
for i := r * r; i <= limit; i += r * r {
isPrime[i] = false
}
}
}
// 收集所有素数
primes := []int{2, 3}
for i := 5; i <= limit; i++ {
if isPrime[i] {
primes = append(primes, i)
}
}
return primes
}
func main() {
limit := 100
primes := atkinSieve(limit)
fmt.Printf("小于等于%d的素数有：n", limit)
fmt.Println(primes)
}
代码逻辑解析
上述实现主要分为三个步骤：
- 初始化标记数组，默认所有数都是合数，先标记2和3为素数，因为这两个数是基础素数，不在后续二次型筛选的范围内。
- 遍历x和y的所有可能取值，根据三个二次型规则对符合条件的n进行标记翻转，满足奇数个解则标记为候选，偶数个则取消标记。
- 遍历所有小于等于sqrt(limit)的候选素数，将其平方的倍数全部标记为合数，避免平方数被误判为素数，最后收集所有标记为素数的数返回。
性能对比与适用场景
对比传统的埃拉托斯特尼筛法，Atkin筛法在N大于10^7时性能优势会逐渐显现，因为它的内层循环次数更少。不过Atkin筛法的实现逻辑更复杂，对于小范围的素数生成，传统筛法的代码更简洁，性能差异也不明显。
实际开发中如果需要生成10^7以上的素数，优先选择Atkin筛法；如果是小范围素数生成，传统筛法更易维护。Go语言的并发特性也可以结合Atkin筛法的逻辑进一步优化，将不同区间的筛选任务分配到多个goroutine执行，提升大范围素数生成的效率。