[Project Euler] Problem 21

Problem 21

素数リストとかは過去の問題のを使い回し。

object P021 {
  val initPrimes:List[Int] = List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
                              31, 37, 41, 43, 47, 53, 59, 61, 67, 
                              71, 73, 79, 83, 89, 97, 101)
  def primes(init:List[Int]):List[Int] = {
    def min(a:Int, b:Int) = if (a<b) a else b
    def sq(a:Int) = a*a
    init ::: List.range(init.last+1, min(100000,sq(init.last))).filter{x => init.forall{x%_!=0}}
  }
  val primeList:List[Int] = primes(primes(initPrimes))
  def factors(n:Int):List[Tuple2[Int,Int]] = {
    def g(n:Int, p:Int, c:Int):Tuple2[Int,Int] = if (n%p==0) g(n/p, p, c+1) else Tuple2(n,c)
    def f(n:Int, ps:List[Int], ts:List[Tuple2[Int,Int]]):List[Tuple2[Int,Int]] = (n,ps) match {
      case (1,_) => ts
      case (_,Nil) => error("n="+n)
      case (_, a::as) if n%a==0 => {
        val z = g(n,a,0)
        f(z._1, as, Tuple2(a,z._2)::ts)
      }
      case (_, a::as) => f(n, as, ts)
    }
    f(n, primeList, Nil)
  }
  def sumDiv(ts:List[Tuple2[Int,Int]]):Int = {
    def pow(a:Int, b:Int):Int = b match {
      case 0 => 1
      case _ => pow(a,b-1)*a
    } 
    def f(t:Tuple2[Int,Int]):Int = {
      List.range(0, t._2 +1).map{pow(t._1, _)}.foldLeft(0)(_+_)
    }
    ts.map(f).foldLeft(1)(_*_)
  }
  def sumDivisors(n:Int):Int = sumDiv(factors(n))-n
  def main(args:Array[String]) {
    println(sumDivisors(220))
    println(sumDivisors(284))
    val l = List.range(2,10000).filter{a => {
      val b=sumDivisors(a)
      val c=sumDivisors(b)
      val r=(a!=b)&&(a==c)
      if (r) println(a+"<->"+b)
      r
    }}
    println(l)
    println(l.foldLeft(0)(_+_))
  }
}

---
　ここまでProject Eulerを解いてきて思ったのだが、組み込みライブラリとか言語仕様で、

• アノテーションを付けるだけで関数の値をメモ化してくれる。
  
• とりあえず1,000,000以下の素数は予め計算されている。
  
• 内部でIntの計算が桁溢れしたら勝手にLong -> BigInt と桁を増やしてくれるような数値型。
  
• 素因数分解も組み込み関数で用意されている。
  

とかだと、かなり楽が出来るのになぁ...。