Scalaでエラトステネスの篩
1 概要
Scalaで,エラトステネスの篩(ふるい)のアルゴリズムを用いて 素数のリストを求める.
1.1 注意
本Webページの作成には Emacs org-mode を用い, 数式等の表示は MathJax を用いています. IEでは正しく表示されないことがあるため, Firefox, Safari等のWebブラウザでJavaScriptを有効にしてお使いください. また org-info.js を利用しており, 「m」キーをタイプするとinfoモードでの表示になります. 利用できるショートカットは「?」で表示されます.
1.2 参考リンク
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