[Project Euler] Problem 3

　Project EulerのProblem 3。

　実のところ、素数列を求める必要は全く無く、単に奇数で順に割って行けば良いだけの問題だと思う。が、せっかくなのでStreamの使い方の勉強という事で、素数列のStreamを作る。

　Streamの使い方は、例えば下記の記事とかが参考になると思う。

• Lazyなリストの作り方 @ Onion開発再開しつつある日記
  
• Scalaで無限リスト：Haskellライクに @ Inforno

　基本的にStreamを使いたいケースというのは、(1)パズル系の問題を解く為に無限数列を作りたい、(2)入力やファイルとかで必要があるまで読み込みたく無い、のどっちかの場合かと思う。勿論、Streamはリストの様に扱え便利なので、ループとかイテレータじゃなくて遅延リストに表現したいという事。
　(1)の場合は、a_n → a_{n+1} = f(a_n) の様に書けるならば、val s = Stream.cons(a0, s.map(f))と書けば良い。Problem 2のような二項漸化式の場合は、s.zip(s.tail)の様な(a_n, a_{n+1})なタプルを作って計算というのが定番。
　(2)の例としては、例えばSimplifying JDBC @ Scala Wikiの例が実用例。JDBCのResultSetをStream[X]に変換するコードとして、

private def strm[X](f: RichResultSet => X, rs: ResultSet): Stream[X] = 
  if (rs.next) Stream.cons(f(new RichResultSet(rs)), strm(f, rs))
  else { rs.close(); Stream.empty };

の様に書かれている。rs.nextがtrueならばStreamの新しい要素xを作って、xとStreamの続きであるstrm(f,rs)自身のconsであるStream.cons(x, strm(f,rs))を返し、rs.nextがfalseになったらEmptyを返して終了。

　Problem 3のコードはこんな感じ。

object P003 {
  def main(args:Array[String]) {
    // println(primes.take(10).force) // -> List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)
    // println(g(13195)) // -> List(29, 13, 7, 5)
    time({println(g(600851475143L))})
  }
  val odds:Stream[Long] = Stream.cons(3, odds.map(_+2))
  def sieve(xs:Stream[Long]):Stream[Long] = Stream.cons(xs.head, sieve(xs.tail.filter{_%(xs.head)!=0}))
  val primes:Stream[Long] = Stream.cons(2, sieve(odds))
  def f(n:Long, ps:Stream[Long], l:List[Long]):(Long,Stream[Long],List[Long]) = {
    if (n==1) (n,ps,l)
    else {
      val m = ps.head
      if (n%m==0) {
        f(n/m, ps, m::l)
      } else {
        f(n, ps.tail, l)
      }
    }
  }
  def g(n:Long):List[Long] = f(n, primes, Nil)._3
  def time(block:Unit) {
    val t0 = System.currentTimeMillis
    block
    println((System.currentTimeMillis-t0)+"msec")
  }
}

　Streamは実際に値が使われるまで計算されないので、デバッグプリントしたいときはtake(10)だけじゃなく、forceとかをつけないと駄目。
　oddsが奇数が無限に続くStreamで、sieveがエラトステネスの篩で素数だけにするフィルタ、primesが素数列です。あとこの問題は素因数分解の対象がIntじゃなくてLongでないと収まらない。最初はIntが駄目なのでBigIntで計算したけど実はLongなんてのもあったな、と計算時間を計るtimeを作っていて思い出したり。