オイラーのφ関数。 n / φ(n) が最大となる n < 1,000,000 を求める。
φ(n) = n より小さく n と互いに素な数の個数(下表)
手始めに素直にφ関数を実装してみる。やってみると分かるが、数が大きくなると全く使えない。本質的に素因数分解と同じなので、大きな素数同士の積になると時間が掛かるのは当然といえば当然か。
方針を変更すべく考えるうちに、逆に素数の積を計算するアプローチがあるのではないかと思い始める。しかし邪道だ。いいんだろうか…?と思い悩みながらも、背に腹は変えられないので計算だけはやってみる。すると一瞬で答えに辿り着く。
こんな方法でいいのかな…。と思っていたら、公式の解法(?)もどうやら同じようである。うーん、ちょっとモヤモヤするが、とりあえずよしとしよう。
まあまあ☆