@minomusi09 さんの「使い方」を原文で引用します: > 自由研究用です。聞かれるので数字を入れるとオイラー関数になります ----v @_0xfffrog- による補足&追加 v---- オイラー函数、(aka トーシェント函数)は、任意の自然数$n$に対して、$n$以下で互いに素な自然数の数を返します。$\phi(n)$と表記されることが多いようです。 このプログラムは、素数32749によって初期化されているので、 32749以下の数: $O(\log n)$で爆速計算 32750以上の数: $O(n\log\log n)$で素数を生成してから計算 です。 一度、32750以上の自然数$n$で計算した後は、($n$以下で最大の素数) 以下の数について爆速計算できます。
-----v ここから下の文章は、LaTeX形式でフォーマットされています v----- @minomusi09 さんのプログラムをもとに、より速く計算できるようにしました。 このプログラムは、Euler's product formula を利用して、オイラー函数を $ \phi(n) = n\prod_{p\mid n} \left(1 - \frac{1}{p}\right) $ として計算しています。 $(\prod_{p\mid n}$とは、$n$が素数$p$で割り切れる場合に、積をとるということです。) このプログラムの方が、なぜ大きい数でも速く計算できるかについて。 ここから、計算量オーダーをランダウのO記法で表記します。 原作は、自然数$m, m<n$に対して、互いに素かを確認してから代入しています。$m$は$n-1$個あって、それぞれの$m$について、互いに素かを確認する作業は (@minomusi09 さんのアルゴリズムだと) $O( e^{\frac{2\log n}{\log\log n}})$ です。(Euclidの互除法を使うと、最大公約数はもっと速く$O(\log n)$で求まります。) これを合わせると、$O(n e^{\frac{2\log n}{\log\log n}})$の計算量があることになります。(Euclidの互除法を使えば$O(n (\log n))$。) 数が小さいうちは、@minomusi09 さんのアルゴリズムの方が速いのですが、大きい数になると少し遅くなってしまいます。 わたしのアルゴリズムは、まず$n$以下の素数を列挙します。ここの計算量は$O(n\log\log n)$です。 次に、$n$以下の素数それぞれが、$n$を割り切るか調べます。$n \mathrm{ mod } p$ (日本語だとnをpで割った余り、というブロックだと思います) が0の時、余りが0なので割り切れると言えます。このときに、定義通り、積をとります。 ここの計算量は$O(\log n)$です。 $\to$ まとめると、素数の列挙から始めるとき、計算量は$O(n\log\log n)$、素数のリストが実行前に与えられているとき、$O(\log n)$です。 わたしのアルゴリズムの方は、小さい数に対してとても遅いというデメリットがあります。しかし、大きい数でもそこまで遅くなりにくいというメリットもあります。 計算量をグラフにしてみました： https://www.desmos.com/calculator/ge8fhgqgon 赤: @minomusi09 さんのプログラム\ 緑: @minomusi09 さんのプログラム+Euclidの互除法\ 黒: わたしのアルゴリズム $(n\ge 32750)$\ 青: わたしのアルゴリズム $(n\lt 32750)$\ このグラフだとn=110あたりでわたしのアルゴリズムが追い抜きます。実際に追い抜く点は1000を超えているので、係数をいじって見やすくしました。ご容赦ください。 (大きくない数(だいたい1000以下)では さんのプログラムの方が優れているということです。)
