ScalaでProject Euler（20）

Problem 12

1から順に素因数分解していきます。偶数なら2で割って、一つずらして掛け算すれば三角数の素因数分解が生成されます。例えば、2³3²を[(2, 3), (3, 2)]と表して、

[] [] [(3, 1)] [(2, 1)]         [(5, 1)]         [(3, 1)]
   [] []       [(3, 1)]         [(2, 1)]         [(5, 1)]
-----------------------------------------------------------------
[] [] [(3, 1)] [(2, 1), (3, 1)] [(2, 1), (5, 1)] [(3, 1), (5, 1)]

type Facts = List[(Int,Int)]

def is_prime(n :Int) = primes.takeWhile(p => p * p <= n).forall(n % _ != 0)
val primes :Stream[Int] = Stream.cons(2, Stream.from(3).filter(is_prime))

def factorize(n :Int) = {
    def f(n :Int, ps :Stream[Int]) :List[Int] = {
        val p = ps.head
        n match {
            case 1 => Nil
            case _ if p * p > n => List(n)
            case _ if n % p == 0 => p :: f(n / p, ps)
            case _ => f(n, ps.tail)
        }
    }
    
    f(n, primes).groupBy((x) => x).toList.map((x) =>(x._1, x._2.length))
}

def half(f :Facts) :Facts = f match {
    case Nil => Nil
    case (2, 1) :: g => g
    case (2, e) :: g => (2, e - 1) :: g
    case h :: g => h :: half(g)
}

def pow(n :Int, e :Int) = (1 to e).foldLeft(1)((x, y) => x * n)

def num_divs(f :Facts) = f.foldLeft(1)((x, y) => x * (y._2 + 1))

def value(f :Facts) =
    f.foldLeft(1)((x, y) => x * pow(y._1, y._2))

val N = 500
val fs = Stream.from(2).map(factorize).map(half)
val nd = fs.zip(fs.tail).map(x => x._1 ++ x._2)
println (nd.filter(x => num_divs(x) > N).map(value).head)