エラトステネスの篩

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

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("")
}

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

^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

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください