分母が1,000,000以下の既約分数は全部でいくつあるか。
問題は を求めることと同義である。ここまで重い計算を避けるために、φ関数を直接計算することは避けてきたが、この問題ではさすがにそうもいかない。連想リストで効率化をはかりつつ、計算は真っ向勝負である。どうかな…と思いながらの挑戦だったが、それでも計算は4-5秒で完了した。
Map.! の利用だけが少々心配である。本来連想リストMapはKeyに対してValueを探し出すが、見つからない可能性もある（失敗するかも知れない）ので、返り値はMaybe a であるが、Map.!はMaybe a 型ではない。いいのだろうか。今回の問題に限って言えば良い。なぜならば、φ関数を2,3...と小さい数から順番に計算して結果を連想リストに覚えていっているので、自分より小さい数をKeyとしたValueは必ず見つかるからである。
まずまず☆
