読者です 読者をやめる 読者になる 読者になる

「プライム・ペア」問題解答 ( CodeIQ )

CodeIQ 数学

CodeIQというところでプログラミング問題「プライム・ペア」に解答しましたので、ネタバレです。

codeiq.jp

問題

今回は次のような問題でした。

  • 標準入力$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$関数、形が綺麗ですね。なので、計算式が分かり易い形に収まりました。