一个有趣的求解质数的golang代码

看到一个golang写的求质数的程序，第一眼看上去很难理解，理解了之后又觉得很有趣，特此分析一下。

代码

package main

import "fmt"

// Send the sequence 2, 3, 4, ... to channel 'ch'.
func generate(ch chan int) {
    for i := 2; ; i++ {
        ch <- i // Send 'i' to channel 'ch'.
    }
}

// Copy the values from channel 'in' to channel 'out',
// removing those divisible by 'prime'.
func filter(in, out chan int, prime int) {
    for {
        i := <-in // Receive value of new variable 'i' from 'in'.
        if i%prime != 0 {
            out <- i // Send 'i' to channel 'out'.
        }
    }
}

// The prime sieve: Daisy-chain filter processes together.
func main() {
    ch := make(chan int) // Create a new channel.
    go generate(ch)      // Start generate() as a goroutine.
    for i:=0; i<20; i++{
        prime := <-ch
        fmt.Print(prime, " ")
        ch1 := make(chan int)
        go filter(ch, ch1, prime)
        ch = ch1
    }
}

分析

首先，求质数（素数）有很多种方法，这个代码用的方法是：

假设有一个数n,已知小于n的所有质数的集合是arr,如果arr中的每个质数都不能够整除n，则n就是质数。这是因为任意一个合数都可以分解成质数的乘积。

例如，

因为 2 是质数，初始化 arr=[2]；

当n=3，3 % 2 != 0, 则 n=3是质数, arr=[2,3]；

当n=4，4 % 2 == 0, 不满足要求，则4不是质数， arr不变；

当n=5,，5 % 2 != 0, 5 % 3 != 0, 则 n=5是质数， arr=[2,3,5];

... 依此类推

两个主要的函数

1. generate函数就是往通道ch中放入n（从2开始）进行筛选。这个ch是没有缓冲区的通道。程序一开始，就启动一个协程执行generate函数（称之为generate协程）。

2. filter函数有三个参数，两个无缓冲区的通道，in和out，和一个质数prime。首先从in中取出一个数据i，如果i不能够被prime整除，则说明它有可能是个质数，则将其放入out通道中。

   重点有两个地方，首先filter函数居然有个for循环（说明不止使用一次），其次，out的数据由谁取？

主逻辑

   for i:=0; i<20; i++{
       prime := <-ch   // [1]
       fmt.Print(prime, " ")
       ch1 := make(chan int)  // [2]
       go filter(ch, ch1, prime)  // [3]
       ch = ch1   // [4]
   }

首先，代码[1]从通道ch中取出一个数2，它必然是质数。代码[2]新建了一个无缓冲的通道ch1，代码[3]启动一个协程运行fliter函数（称之为fliter1协程），其中参数in是ch，out是ch1，prime是2，语句[4]是将通道ch赋值为了通道ch1，然后又转到了语句[1]，这实质上就是从ch1中取数据，也其实就是从fliter1协程的out通道取数据。

fliter1协程的in通道会接收到数字3（由generate协程放入），经过判断，将3放入了out通道。在语句[1]中，从ch也就是out通道中取出3并打印。

当判断数字3时，如图所示：

输入3时 .png

打印出数字3之后，又启动了一个协程运行fliter函数，称之为fliter2协程，它的参数in是通道ch，实际上就是之前的ch1，也就是fliter1协程的out通道！而out通道最后又赋值给了ch。而这时的prime变成了3。这样做显而易见，因为再次新来一个数的时候，不仅需要看能不能被2整除（由fliter1协程判断），还要看能不能被3整除（由fliter2协程判断）。

当判断数字4时，由于fliter1协程判断不通过，所有并没有放入fliter2协程，语句[1]也就不能取出数，就会阻塞。

当判断数字5时，传入fliter1协程，通过，再次传入fliter2协程，继续判断通过，从out通道传出，实际上就是语句[1]的ch通道，所有打印出5。

当判断数字5时，如图所示：

输入5时.png

所以，可以推理出，数字n前面有m个质数，就会产生m个fliter协程，这些协程串联在一起，每个协程负责判断能否被某个质数整除，如果不能，则传递个给下一个协程进行判断，直至输出。

总结

• ch=ch1的时候，原先的ch并没有消失，还被之前启动的fliter协程保存着。
• 巧妙使用通道的性质，将多个协程进行串联。
• 最开始我还以为是一个并行的筛选质数的代码，结果并不是，其实是串行执行。