筛子算法之golang实现求素数解析

最近在熟悉go相关方面的知识，在这本书看到协程通道的一个demo， 短短几行代码，本人才疏学浅理解了大半天才把思路缕明白， 领悟之后顿感这几行代码的算法精妙、行行珠玑

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 {
        prime := <-ch
        fmt.Print(prime, " \n")
        ch1 := make(chan int)
        go filter(ch, ch1, prime)
        ch = ch1
    }
}

简单的把原理先说出来，感兴趣的小伙伴在知道原理后可以先不要往下看，直接去看代码理解一下：
这是一个求素数的程序，所谓素数就是除了1和自身以外，不能整除其他自然数的数,一个自然数如果不能被其它所有小于它的素数整除也称为素数，本例中就是用这些特性来求素数
设一个从二到无穷大的自然数数据流，逐级递增，先求出最小的素数，拿到该素数作为筛子，然后筛出比筛子大的最小素数，把这个筛选出的素数再次当作筛子，以此类推...

shaizi.png

下面分析代码：
generate这个函数很简单，用作产生无穷个从2依次递增的自然数

filter函数乍看也很简单，签名参数是两个通道和一个已知的素数，函数中是一个无限循环，每一轮循环中从输入通道in拿到待筛选的数据流，然后除以素数prime,不能整除的话则把被除数放入输出通道out，否则忽略掉被操作数，然后进入下一轮循环往复操作

其实这里的filter就可以具体的看作一个个筛子了，功能就是筛出当前素数无法整除的数然后流向下一个筛子，从宏观的角度来讲，这一个个筛子刚好组成了素数队列...

主函数main:创建数据流通道ch，注意在go中通道都是以指针形式（即通道的地址）来操作的
然后在一个协程中不停的生成数据流

接下来是一个无限循环，循环中从当前的数据流通道ch取出最小的那个数，这个数prime即是素数（这里应该会有很多小伙伴产生疑惑），然后创建一个输出通道ch1

开启一个协程，把输入数据流ch、创建的ch1、以及刚刚拿到的素数传入filter，用来筛选数据流(在程序运行很久之后会产生无数个filter的协程，这一个个协程可以形象地看作一个个筛子)

在循环的最后一步，把ch1赋值给ch，这一步很重要，是为了下一步循环做铺垫，所谓的赋值，即是把下一轮的数据流ch指定为本轮的输出流ch1：本轮输出流流向下轮输入流，如此往复...

主函数main是比较难以理解的，在每一轮循环中都会产生唯一的一个素数，这个素数用来筛选出上一轮流过来的数据流并流向下一轮

// 第一轮  筛子2
3 5 7 9 11 13...
// 第二轮  筛子3
5 7 11 13...
//第三轮 筛子5
7 11 13 17 19...

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

整套从程序有三个无限循环分别在三个协程中，本来很简单，但是循环一嵌套，就会显得复杂起来

还在迷糊的小伙伴可以把代码拷贝加入调试信息观察一下
已经搞定的小伙可以看一下以上代码的包装版加强理解：

package main

import "fmt"

func generator() chan int{
    ch := make(chan int)
    go func() {
        for i:=2; ;i++{
            ch <- i
        }
    }()
    return ch
}

func filter3(in chan int, primer int) chan int{
    out := make(chan int)
    go func() {
        for {
            i:= <- in
            if i%primer != 0{
                out <- i
            }
        }
    }()
    return out
}


func sieve2() chan int{
    out := make(chan int)

    go func() {
        ch := generator()
        for {
            prime := <- ch
            ch = filter3(ch, prime)
            out <- prime
        }
    }()
    return out
}

func main(){
    primes := sieve2()
    for{
        fmt.Println(<-primes)
    }

}

最后普及一下golang语法的某些特点：
上例中创建的通道，都是默认的无缓冲通道，特点是如果通道中有数据，再往通道中放数据的话，程序会一直阻塞，直到通道中的数据被取出，操作不当容易产生死锁问题
如果用range遍历通道的话，如果通道中没有数据，程序会阻塞在range处，直到该通道被关闭

关于协程：
不了解协程的话可以把协程想象成打开一个新电脑同步运行协程中的代码，无数个协程运行即无数个电脑在运行，这些电脑（协程）之间同步通信的方式即是用通道