pub trait EulerPhi {
// Required method
fn euler_phi(self) -> Self;
}Expand description
Euler の $\varphi$ 関数。
$n$ 以下の自然数のうち、$n$ と互いに素であるものの個数を返す。$1$ と $1$ は互いに素であることに注意。
Note
素数冪 $p^k$, $p'^{k'}$ ($p\ne p'$) について $\varphi(p^k p'^{k'}) = \varphi(p^k)\varphi(p'^{k'})$ が成り立つ。また、$\varphi(p^k) = \varphi^{k-1}\cdot(p-1)$ が成り立つ。
Complexity
$O(\sqrt{n})$ time.
Examples
use nekolib::math::EulerPhi;
assert_eq!(1_u64.euler_phi(), 1);
assert_eq!(60_u64.euler_phi(), 16);