Trait nekolib::math::euler_phi::EulerPhi

pub trait EulerPhi {
    // Required method
    fn euler_phi(self) -> Self;
}

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

fn euler_phi(self) -> Self

Implementations on Foreign Types

impl EulerPhi for u128

fn euler_phi(self) -> Self

impl EulerPhi for u32

fn euler_phi(self) -> Self

impl EulerPhi for u16

fn euler_phi(self) -> Self

impl EulerPhi for u64

fn euler_phi(self) -> Self

impl EulerPhi for usize

fn euler_phi(self) -> Self

impl EulerPhi for u8

fn euler_phi(self) -> Self

Implementors