オイラーのφ関数
説明
正の整数 $n$ に対して, $1$ から $n$ までの自然数のうち $n$ と互いに素なものの個数を $\phi(n)$ として与えることに酔って定まる数論的関数 $\phi$ である。
計算量
値 $O(\sqrt N)$
テーブル $O(N \log \log N)$
実装例
正の整数 $n$ に対して, $1$ から $n$ までの自然数のうち $n$ と互いに素なものの個数を $\phi(n)$ として与えることに酔って定まる数論的関数 $\phi$ である。
値 $O(\sqrt N)$
テーブル $O(N \log \log N)$