こちらのエントリ
もしぼくが採用するなら
を読んで、エラトステネスの篩は知ってはいるものの実装してみたことないなぁと思い、
Scalaで実装してみました。
Wikipedia の例題を参考に作ってみます。
考え方としては自然数の集合に対して、小さい順からその倍数を削除していって、
残ったものが素数、という考えです。
最初、こんな感じで実装してみました。
末尾再帰じゃないバージョン 1
2
3
4
5
6
7
8
9
10
11
12
13
def sieveOfEratosthenes ( numbers : List [ Int ]) : List [ Int ] = {
numbers match {
case Nil =>
Nil
case 1 :: tail =>
sieveOfEratosthenes ( tail )
case head :: tail =>
head :: sieveOfEratosthenes ( tail . filterNot ( _ % head == 0 ))
}
}
// 実行
println ( sieveOfEratosthenes ( Range ( 1 , 121 ). toList ))
まあこれで動くには動くのですが、最後で再帰の結果に対して演算しているので末尾再帰されてません（@tailrecつけるとコンパイルエラーになる）。
なので数が多くなるとOutOfMemoryで落ちます。
いろいろ考えて、素数の結果リストを引数で渡すようにしました。
末尾再帰バージョン 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import scala.annotation.tailrec
@tailrec
def sieveOfEratosthenes ( numbers : List [ Int ], primes : List [ Int ]) : ( List [ Int ], List [ Int ]) = {
numbers match {
case Nil =>
( numbers , primes . reverse )
case 1 :: tail =>
sieveOfEratosthenes ( tail , primes )
case head :: tail =>
sieveOfEratosthenes ( tail . filterNot ( _ % head == 0 ), head :: primes )
}
}
// 実行
sieveOfEratosthenes ( Range ( 1 , 120 ). toList , Nil ). _2
末尾再帰になった！しかし実行時に引数にNilを渡したり、結果がタプルなので結果取得にひと手間かかったり、かっこ悪すぎ。
末尾再帰バージョン（呼び出しをシンプルに） 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import scala.annotation.tailrec
def sieveOfEratosthenes ( numbers : List [ Int ]) : List [ Int ] = {
@tailrec
def sieve ( numbers : List [ Int ], primes : List [ Int ]) : ( List [ Int ], List [ Int ]) = {
numbers match {
case Nil =>
( numbers , primes . reverse )
case 1 :: tail =>
sieve ( tail , primes )
case head :: tail =>
sieve ( tail . filterNot ( _ % head == 0 ), head :: primes )
}
}
sieve ( numbers , Nil ). _2
}
// 実行
println ( sieveOfEratosthenes ( Range ( 1 , 121 ). toList ))
できたけどなんかゴチャゴチャしてる感じがありますね・・・。きっともっと素敵な書き方があるはず。Sieve of Eratosthenes in Scala
