Scalaでエラトステネスの篩

Table of Contents

1 概要

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

1.1 注意

本Webページの作成には Emacs org-mode を用い, 数式等の表示は MathJax を用いています. IEでは正しく表示されないことがあるため, Firefox, Safari等のWebブラウザでJavaScriptを有効にしてお使いください. また org-info.js を利用しており, 「m」キーをタイプするとinfoモードでの表示になります. 利用できるショートカットは「?」で表示されます.

2 Range

まず,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)

3 filter

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

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

4 sieve

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

 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

5 遅延評価

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

Date: 2013-08-06 12:56:14 JST

Author: 田村直之

Validate XHTML 1.0