ScalaでProject Euler（104）

Scala

Problem 69

オイラーのφ関数は前に書いたように、

n = p_1^{e_1} \cdots p_m^{e_m}
\varphi(n) = n(1-\frac{1}{p_1})\cdots(1-\frac{1}{p_m})

なので、

n / \varphi(n) = \frac{p_1}{p_1-1}\cdots\frac{p_m}{p_m-1}

です。素数を昇順に掛けていくだけですね。

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

def primes() =
    Iterator.from(2).filter(is_prime)

val N = 1e6.toInt
println (Iterator.iterate((1, primes))(x => (x._1 * x._2.next(), x._2)).
                                            map(_._1).takeWhile(N >=).max)