[Project Euler] Problem 12

Problem 12

　最初に素数列を作成するのに結構時間がかかる気がする。今回は最初10000以下の素数のリストを作り、エラーが出たので30000まで作った。
　約数の数は素因数分解して各素数の指数から求められるのを使う。

object P012 {
  val maxRange = 30000
  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(maxRange,sq(init.last))).filter{x => init.forall{x%_!=0}}
  }
  val primeList = primes(primes(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)))
  val emptyFactors = primeList.map{x => 0}
  def factor(n:Int):List[Int] = {
    def f(x:Int, fs:List[Int], ps:List[Int]):List[Int] = (x,fs,ps) match {
      case (1,_,_) => fs
      case (_,Nil,_) => error("fs empty:x="+x)
      case (_,_,Nil) => error("ps empty:x="+x)
      case (y,a::as,b::bs) if y%b==0 => f(y/b, (a+1)::as, ps)
      case (y,a::as,b::bs)           => a::f(y,as,bs)
    }
    f(n, emptyFactors, primeList)
  }
  def numFactors(n:Int):Int = factor(n).foldLeft(1){(a,b) => a*(b+1)}
  def triangle(n:Int):Int = n*(n+1)/2
  def main(args:Array[String]) {
    println(primeList.length)
    println(numFactors(28))
    val t:Tuple3[Int,Int,Int] =
      Stream.range(1,maxRange).map{x => Tuple3(x,triangle(x),numFactors(triangle(x)))}.filter{x => x._3>500}.head
    println(t)
    println(factor(triangle(t._1)).zip(primeList).filter{t => t._1 != 0}.map{x => x._2+"^"+x._1})
  }
}