golang生成素数

本文示例参考《Go语言高级编程》的生成思路，因为在看书过程中，此处理解了很久，特此记录以下。

素数是除了1和其本身公约数之外，没有其他公约数，也就是不能整除其他整数。

设一个从二到无穷大的自然数数据流，逐级递增，先求出最小的素数，拿到该素数作为筛子，然后筛出比筛子大的最小素数，把这个筛选出的素数再次当作筛子，以此类推…

demo

package main

import "fmt"

// GenerateNatural 从最小素数开始生成自然数
func GenerateNatural() <-chan int {
	ch := make(chan int)
	go func() {
		for i := 2; ; i++ {
			ch <- i
		}
	}()
	return ch
}

// filter 通过较小的素数得到较大的素数
func filter(in <-chan int, prime int) <-chan int {
	out := make(chan int)
	go func() {
		for {
			if v := <-in; v%prime != 0 {
				out <- v
			}
		}
	}()
	return out
}

func main() {
	ch := GenerateNatural()
	for i := 0; i < 100; i++ {
		p := <-ch
		fmt.Printf("seq = %d, num = %d\n", i+1, p)
		ch = filter(ch, p)
	}
}

分析

通过GenerateNatural 生成最小素数2及以后的自然数，2,3,4,5,6,7,8,9,10,11…,此时将2作为筛选因子过滤出i%2 != 0的，即：3,5,7,9,11..；此时筛选因子变为3，筛选剩余的5,7,9,11, 通过 i%3 != 0,得到 5,7,11…，此时，筛选因子又变成5,依次类推；得到每次的筛选因子列表就是素数列表。

每一轮数据流中最小的那个就是素数，原理是：一个素数不能整除的那个比它自身大的最小的那个数就是素数<比如说素数2可以得出素数3， 素数3可以得出素数5， 5求出7…>

参考

• 《Go语言高级编程》
• https://studygolang.com/articles/16413?fr=sidebar