Scalaでエラトステネスの篩

Scalaで，エラトステネスの篩(ふるい)のアルゴリズムを用いて 素数のリストを求める．

まず，2以上n未満の整数のリストはRangeで生成できる (2 until n でも良い)．

scala> Range(2, 10).toList
res: List[Int] = List(2, 3, 4, 5, 6, 7, 8, 9)
scala> (2 until 10).toList
res: List[Int] = List(2, 3, 4, 5, 6, 7, 8, 9)

与えられた整数で割り切れる数をリストから取り除くにはfilterを用いる．

scala> Range(2, 10).toList.filter(_ % 2 != 0)
res: List[Int] = List(3, 5, 7, 9)

エラトステネスの篩を実装する．

 1:  object Sieve {
 2:    def sieve(xs: List[Int]): List[Int] =
 3:      if (xs.isEmpty)
 4:        Nil
 5:      else
 6:        xs.head :: sieve(xs.tail.filter(_ % xs.head != 0))
 7:  
 8:    def primes(n: Int) = sieve(Range(2, n).toList)
 9:  
10:    def main(args: Array[String]) {
11:      primes(100).foreach { println }
12:    }
13:  }

コンパイルして実行する．

$ scalac Sieve.scala
$ scala Sieve
2
3
5
...
97

Range(m, n)は，m以上n未満の整数のリストを生成するが， あらかじめ上限nを定めないといけない．

遅延評価 (lazy evaluation)のメカニズムを用いると， 無限の長さのリストを取り扱うことが可能になる． 遅延評価は，必要が生じるまで計算を遅延させるというメカニズムである．

Scalaで遅延評価を行うには，Listの代わりにStreamを用いる．

以下の関数fromは，n以上の整数の無限Streamを生成する．

def from(n: Int): Stream[Int] = Stream.cons(n, from(n + 1))  

以下のようにすると2以上の整数の最初の5個を印刷できる．

scala> from(2).take(5).print
2, 3, 4, 5, 6, empty

以下は，2以上の整数で偶数を除いた最初の5個を印刷している．

scala> from(2).filter(_ % 2 != 0).take(5).print
3, 5, 7, 9, 11, empty

遅延評価版のプログラムLazySieveは以下のようになる．

 1:  object LazySieve {
 2:    def from(n: Int): Stream[Int] =
 3:      Stream.cons(n, from(n + 1))  
 4:  
 5:    def sieve(xs: Stream[Int]): Stream[Int] =
 6:      Stream.cons(xs.head, sieve(xs.tail.filter(_ % xs.head != 0)))
 7:  
 8:    def primes = sieve(from(2))
 9:  
10:    def main(args: Array[String]) {
11:      primes.take(10).foreach { println }
12:    }
13:  }

以下が実行結果である． 最初の10個の素数を印刷している．

$ scalac LazySieve.scala
$ scala LazySieve
2
3
...
29

また，REPLからは，以下のように実行できる．

scala> LazySieve.primes.take(5).print
2, 3, 5, 7, 11, empty

scala> LazySieve.primes(0)    // 1番目の素数
res: Int = 2

scala> LazySieve.primes(304)  // 305番目の素数
res: Int = 2011

scala> LazySieve.primes.filter(_ >= 2000).head  // 2000以上の最初の素数
res: Int = 2003

scala> LazySieve.primes.takeWhile(_ <= 2000).size // 2000以下の素数の個数
res: Int = 303