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);

Required Methods§

source

fn euler_phi(self) -> Self

Implementations on Foreign Types§

source§

impl EulerPhi for u128

source§

fn euler_phi(self) -> Self

source§

impl EulerPhi for u32

source§

fn euler_phi(self) -> Self

source§

impl EulerPhi for u16

source§

fn euler_phi(self) -> Self

source§

impl EulerPhi for u64

source§

fn euler_phi(self) -> Self

source§

impl EulerPhi for usize

source§

fn euler_phi(self) -> Self

source§

impl EulerPhi for u8

source§

fn euler_phi(self) -> Self

Implementors§