ScalaでProject Euler（105）

Problem 70

とりあえず、素直に解いてみましょう。ふるい的に素因数分解して、全ての対象の整数についてφを求め並べ替えになっているか調べ、n/φ(n)が最小のものを選びます。
これで10秒です。Pythonでは16倍くらい遅かったです。

import scala.testing.Benchmark

type Facts = List[(Int,Int)]

val N :Int = 1e7.toInt

object Factorize {
    private val fs = new Array[Int](N)
    for(n <- 2 to N - 1) fs(n) = n
    for(p <- Iterator.from(2).takeWhile(p => p * p < N) if fs(p) == p;
        k <- Iterator.range(p * 2, N, p))
            fs(k) = p
    
    def apply(n :Int) :Facts = {
        if(n == 1)
            Nil
        else {
            val p = fs(n)
            val (e, m) = div_pow(n, p)
            (p, e) :: apply(m)
        }
    }
    
    def div_pow(n :Int, d :Int) :(Int,Int) =
        if(n % d != 0)
            (0, n)
        else {
            val (e, m) = div_pow(n / d, d)
            (e + 1, m)
        }
}

def phi(n :Int) :Int =
    Factorize(n).foldLeft(n)((m, x) => m / x._1 * (x._1 - 1))

def digits(n :Int) :List[Int] =
    if(n == 0) Nil else n % 10 :: digits(n / 10)

def sorted_digits(n :Int) :List[Int] =
    digits(n).sortWith(_ < _)

def is_permutation(m :Int, n :Int) :Boolean =
    sorted_digits(m) == sorted_digits(n)

def solve() = {
    println (Iterator.range(2, N).map(n => (n, phi(n))).
                filter(x => is_permutation(x._1, x._2)).
                map(x => (x._1.toDouble / x._2, x._1)).min)
}

object Test extends Benchmark {
    def run() = solve
}

println (Test.runBenchmark(3))