Go素数筛选分析

1. 素数筛选介绍

学习Go语言的过程中，遇到素数筛选的问题。这是一个经典的并发编程问题，是某大佬的代码，短短几行代码就实现了素数筛选。但是自己看完原理和代码后一脸懵逼（仅此几行能实现素数筛选），然后在网上查询相关资料，依旧似懂非懂。经过1天的分析调试，目前基本上掌握了的原理。在这里介绍一下学习理解的过程。

素数筛选基本原理如下图：

就原理来说还是比较简单的，首先生成从 2 开始的递增自然数，然后依次对生成的第 1, 2, 3, ...个素数 整除，经过全部整除仍有余数的自然数，将会是素数。

大佬的代码如下：

// 返回生成自然数序列的管道: 2, 3, 4, ...
// GenerateNatural 函数内部启动一个 Goroutine 生产序列，返回对应的管道
func GenerateNatural() chan int {
	ch := make(chan int)
	go func() {
		for i := 2; ; i++ {
			ch <- i
		}
	}()
	return ch
}
// 管道过滤器: 将输入序列中是素数倍数的数淘汰，并返回新的管道
// 函数内部启动一个 Goroutine 生产序列，返回过滤后序列对应的管道
func PrimeFilter(in <-chan int, prime int) chan int {
	out := make(chan int)
	go func() {
		for {
			if i := <-in; i%prime != 0 {
				out <- i
			}
		}
	}()
	return out
}
func main() {
	ch := GenerateNatural() // 自然数序列: 2, 3, 4, ...
	for i := 0; i < 100; i++ {
		prime := <-ch // 新出现的素数
		fmt.Printf("%v: %v\n", i+1, prime)
		ch = PrimeFilter(ch, prime) // 基于新素数构造的过滤器
	}
}

main()函数先是调用 GenerateNatural() 生成最原始的从 2 开始的自然数序列。然后开始一个 100 次迭代的循环，希望生成 100 个素数。在每次循环迭代开始的时候，管道中的第一个数必定是素数，我们先读取并打印这个素数。然后基于管道中剩余的数列，并以当前取出的素数为筛子过滤后面的素数。不同的素数筛子对应的管道是串联在一起的。

运行代码，程序正确输出如下：

1: 2
2: 3
3: 5
......
......
98: 521
99: 523
100: 541

2. 代码分析

之前在课本中学习到：chan底层结构 是一个指针，所以我们能在函数间直接传递 channel，而不用传递 channel 的指针。

上述代码fun GenerateNatural()中创建了管道ch := make(chan int)，并创建一个协程（为了便于描述，该协程称为Gen）持续向ch中写入渐增自然数。

当i=0时，main()中prime := <-ch读取该ch（此时prime=2，输出素数2），接着将ch传入PrimeFilter(ch, prime)中。PrimeFilter(ch, prime)创建新协程（称为PF(ch, 2)）持续读取传入的ch（ch中2之前已被取出，从3依次往后读取），同时返回一个新的chan out（当通过过滤器的i向out写入时，此时out仅有写入而没有读取操作，PF(ch, 2)将阻塞在第1次写chan out操作）。与此同时main()中ch = PrimeFilter(ch, 2)将out赋值给ch，此操作给ch赋了新变量。到这里，重点来了：由于在随后的时间里，协程Gen、PF(ch, 2)中仍需要不停写入和读取ch，这里将out赋值给ch的操作是否会更改Gen、PF(ch, 2)两协程中ch的值了？

直接给出答案（后面会给出代码测试），此时ch赋新值不影响Gen、PF(ch, 2)两协程，仅影响main() for循环体随后对chan的操作。（本人认为go中channel参数传递采用了channel指针的拷贝，后续给channel赋新值相当于将该channel重新指向了另外一个地址，该channel与之前协程中使用的channel分别指向不同地址，是完全不同的变量）。为了便于后面分析，这里将ch = PrimeFilter(ch, 2)赋值后的ch称为ch_2。

当i=1时，main() for循环读取前一次产生新的ch_2赋值给prime（此时prime=3，输出素数3），接着将ch_2传入PrimeFilter(ch, prime)并创建新协程（称为PF(ch, 3)），而后ch = PrimeFilter(ch, 3)将新产生的out赋值给ch，称为ch_3。与此同时协程Gen持续向ch中写入直至阻塞，携程PF(ch, 2)持续读取ch值并写入ch_2直至阻塞，新协程PF(ch, 3)持续读取ch_2值并输出至chan out（即ch_3）（此时ch_3仅有写入而没有读取操作，PF(ch, 3)将阻塞在第1次写ch_3操作）。

当i继续增加时，后面的结果以此类推。

总结一下：main()函数中，每循环1次，会增加一个协程PF(ch, prime)，且协程Gen与新增加的协程之间是串联的关系（即前一个协程的输出，作为下一个协程的输入，二者通过channel交互），协程main每次循环读取最后一个channel的第1个值，获取prime素数。基本原理如下图所示。

3. 代码验证

(1) channel参数传递验证

func main() {
	ch1 := make(chan int)
	go write(ch1)
	go read(ch1)
	time.Sleep(time.Second * 3)
	fmt.Println("main() 1", ch1)
	ch2 := make(chan int)
    ch1 = ch2
	fmt.Println("main() 2", ch1)
	time.Sleep(time.Second * 3)
}

func read(ch1 chan int) {
	for {
		time.Sleep(time.Second)
		fmt.Println("read", <-ch1, ch1)
	}
}
func write(ch1 chan int) {
	for {
		time.Sleep(time.Second)
		fmt.Println("write", ch1)
		ch1 <- 5
	}
}

测试代码比较简单，在main()中创建chan ch1，后创建两个协程write、read分别对ch1不间断写入与读取，持续一段时间后，main()新创建ch2，并赋值给ch1，查看协程write、read是否受到影响。

...
write 0xc000048120
read 5 0xc000048120
main() 1 0xc000048120
main() 2 0xc000112000
write 0xc000048120
read 5 0xc000048120
...

程序输出如上，可以看到ch1地址为0x