エラトステネスの篩

前回のエントリで作った makeInt と streamFileter を使って、素数列を生成するプログラムを作ってみよう。「エラトステネスの篩」というアルゴリズムを使う。
まずはコード。

package main

import (
    "fmt"
)

type Stream chan int

func makeInt(n, m int) Stream {
    s := make(Stream)
    go func() {
        for i := n; i <= m; i++ {
            s <- i
        }
        close(s)
    }()
    return s
}

func streamFilter(f func(int) bool, in Stream) Stream {
    s := make(Stream)
    go func() {
        for {
            x, ok := <- in
            if !ok {
                break
            }
            if f(x) {
                s <- x
            }
        }
        close(s)
    }()
    return s
}

func filter(n int, in Stream) Stream {
    return streamFilter(func(x int) bool {
        return x % n != 0
    }, in)
}

func seive(n int) Stream {
    s := make(Stream)
    go func() {
        in := makeInt(2, n)
        for {
            x, ok := <- in
            if !ok {
                break
            }
            s <- x
            if x * x <= n {
                in = streamFilter(func(y int) bool {
                    return y % x != 0
                }, in)
            }
        }
        close(s)
    }()
    return s
}

func main() {
    for x := range seive(500) {
        fmt.Print(x, " ")
    }
    fmt.Println("")
}

makeInt と streamFilter は前回と同じだ。篩にあたる seive が素数列を生成する。
まずはストリームを用意しておく（変数 s）。で、ゴルーチンを起動して、中で 2 から始まる整数列を生成するストリームを in に代入する。ここからは繰り返しで、in の先頭 x は素数なのでそのまま s に送信する。そして in を x で割り切れる数を取り除くフィルタをかけたストリームに置き換える。これで in は x で割り切れない数列を生成するストリームになった。
結果として素数以外はストリームから取り除かれて、素数だけが残るっていうわけだ。
実行結果。

^o^ > go run eratosthenes.go
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499