nekolib/math/
euler_phi.rs

1//! Euler の $\\varphi$ 関数。
2
3use super::factors;
4
5use factors::Factors;
6
7/// Euler の $\\varphi$ 関数。
8///
9/// $n$ 以下の自然数のうち、$n$ と互いに素であるものの個数を返す。$1$
10/// と $1$ は互いに素であることに注意。
11///
12/// # Note
13/// 素数冪 $p^k$, $p\'^{k\'}$ ($p\\ne p\'$) について
14/// $\\varphi(p^k p\'^{k\'}) = \\varphi(p^k)\\varphi(p\'^{k\'})$
15/// が成り立つ。また、$\\varphi(p^k) = \\varphi^{k-1}\\cdot(p-1)$ が成り立つ。
16///
17/// # Complexity
18/// $O(\\sqrt{n})$ time.
19///
20/// # Examples
21/// ```
22/// use nekolib::math::EulerPhi;
23///
24/// assert_eq!(1_u64.euler_phi(), 1);
25/// assert_eq!(60_u64.euler_phi(), 16);
26/// ```
27pub trait EulerPhi {
28    fn euler_phi(self) -> Self;
29}
30
31macro_rules! impl_uint {
32    ($t:ty) => {
33        impl EulerPhi for $t {
34            fn euler_phi(self) -> Self {
35                self.factors().map(|(p, e)| p.pow(e - 1) * (p - 1)).product()
36            }
37        }
38    };
39    ( $($t:ty)* ) => { $(impl_uint!($t);)* };
40}
41
42impl_uint!(u8 u16 u32 u64 u128 usize);
43
44#[test]
45fn test_naive() {
46    use gcd::Gcd;
47    let n = 100_usize;
48    for i in 1..=n {
49        let phi = (1..=i).filter(|&j| i.gcd(j) == 1).count();
50        assert_eq!(i.euler_phi(), phi);
51    }
52}
nekolib/math/euler_phi.rs

nekolib/math/
euler_phi.rs
