「プライム・ペア」問題解答 ( CodeIQ )
CodeIQというところでプログラミング問題「プライム・ペア」に解答しましたので、ネタバレです。
問題
今回は次のような問題でした。
- 標準入力$n$に対して、$\phi(n!)$ を1000003で割った余りを出力する。なお、$\phi$はオイラーの$\phi$関数、$\phi(k)$=($k$以下で$k$と互いに素な自然数の個数 )
解説
オイラーのφ関数 - Wikipedia にもある通り、 $$ \phi(k)=k\prod_{p:prime,\,p\nmid k}\frac{p -1}{p} $$
が成り立ちます。例えば、12の素因数は2,3ですから、$\phi(12)=12\cdot \frac{2-1}{2}\cdot\frac{3-1}{3}=4$ です。
ところで、今回のように階乗の値が引数にある場合はどうなるでしょうか?
$\phi(12!)$ であれば、この階乗の素因数は12以下の素数、2,3,5,7,11ですから、
$$
\begin{eqnarray}
\phi(12!)&=&12!\cdot\frac{2-1}{2}\cdot\frac{3-1}{3}\cdot\frac{5-1}{5}\cdot\frac{7-1}{7}\cdot\frac{11-1}{11} \\
\, &=&1\cdot (2-1)\cdot (3-1)\cdot 4\cdot (5-1)\cdot 6\cdot (7-1)\cdot 8\cdot 9\cdot 10\cdot (11-1)\cdot 12
\end{eqnarray}
$$
ということは、$\phi(n!)$は、$n$以下の自然数に対して、素数は1引いて、非素数はそのまま掛け合わせた数であると分かります。
なので、Rubyでnaiveに表現すると(1..n).reduce{|s,e|s*(e.prime? ? e-1 : e)%1000003}
のような計算になるのですが、流石に毎回 prime? で判定するのは遅いので、素数の一覧から、掛け合わせる数のリストを作るEnumeratorを使う実装としました。
require'prime' p ->n{ Enumerator.new{|y| t=1 Prime.each(n){|q| (t...q).each{|i|y<<i} y<<(q-1) t=q+1 } (t..n).each{|i|y<<i} }.reduce{|s,i|s*i%1000003} }[gets.to_i]
終わりに
オイラーの$\phi$関数、形が綺麗ですね。なので、計算式が分かり易い形に収まりました。