dsalgo 0.3.10

A package for Datastructures and Algorithms.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

/// number of 1 <= k <= n, gcd(k, n) = 1.

pub fn euler_totient<F>(
    factorize: &F,
    mut n: u64,
) -> u64
where
    F: Fn(u64) -> Vec<(u64, u8)>,
{
    for (p, _) in factorize(n as u64) {
        debug_assert_eq!(n % p, 0);

        n -= n / p;
    }

    n
}

#[cfg(test)]

mod tests {

    #[test]

    fn test() {
        use super::*;
        use crate::prime_factorize_trial_division::*;

        // https://oeis.org/A000010
        const PHI: &'static [u64] = &[
            1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12,
            10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18,
            24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, 32, 24, 52, 18, 40,
            24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66, 32, 44,
        ];

        for i in 0..PHI.len() {
            assert_eq!(euler_totient(&prime_factorize, (i + 1) as u64), PHI[i]);
        }
    }
}