ScalaでProject Euler(45)

Problem 26

この問題は以前に詳しく説明しました。

Project Euler 26 - 桃の天然水

要約すると、

d素数でなければならない
10n ≡ 1(mod d)となる最小の自然数nd-1でなければならない
上の合同式が成り立つnd-1の約数のみ

だから、d-1以外の全ての約数について上の合同式が成り立たないような最も大きいdを求めればよいのでした。
しかし、もう少し考えるとd-1から一つずつ素因数を取り除いた数、すなわち例えば

d - 1 = 23・32・5

だとすると、

22・32・5
23・3・5
23・32

の3つについて調べていずれも合同式が成り立たないことを確かめればよいです。
もっとも、この計算より素数判定のほうがずっと遅くて、速度的には約数全部調べるのとあまり変わらないのではないかと思います。

import scala.testing.Benchmark

def is_prime(n :Int) =
    Iterator.from(2).takeWhile(m => m * m <= n).forall(n % _ != 0)

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

def pow(n :Int, e :Int, d :Int) :Int =
    if(e == 0)
        1
    else {
        val m = pow(n, e / 2, d)
        if(e % 2 == 1)
            (m.toLong * m * n % d).toInt
        else
            (m.toLong * m % d).toInt
    }

def is_full_length(n :Int) =
    is_prime(n) &&
        factorize(n - 1).map((n - 1) / _._1).forall(pow(10, _, n) != 1)

def solve() = {
    val N = 1e9.toInt
    println (Iterator.range(N - 1, 1, -1).filter(is_full_length).next)
}

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

println (Test.runBenchmark(10))