haar_lib/math/
totient.rs

1//! トーシェント関数
2//!
3//! # References
4//! - <https://ja.wikipedia.org/wiki/%E3%82%AA%E3%82%A4%E3%83%A9%E3%83%BC%E3%81%AE%CF%86%E9%96%A2%E6%95%B0>
5
6/// `n`と互いに素である自然数の個数を求める。
7pub fn totient(mut n: u64) -> u64 {
8    let mut ret = n;
9
10    let mut i = 2;
11    while i * i <= n {
12        if n % i == 0 {
13            ret -= ret / i;
14            while n % i == 0 {
15                n /= i;
16            }
17        }
18
19        i += 1;
20    }
21
22    if n != 1 {
23        ret -= ret / n;
24    }
25
26    ret
27}
28
29/// `n`までのトーシェント関数のテーブル$\varphi$を構築する。
30///
31/// nとmが互いに素のとき、$\varphi(nm) = \varphi(n) \cdot \varphi(m)$
32pub fn totient_table(n: usize) -> Vec<u64> {
33    let mut ret = (0..=n as u64).collect::<Vec<_>>();
34
35    for i in 2..=n {
36        if ret[i] == i as u64 {
37            for j in (i..=n).step_by(i) {
38                ret[j] = ret[j] / (i as u64) * (i as u64 - 1);
39            }
40        }
41    }
42
43    ret
44}
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn test() {
52        // https://oeis.org/A000010/list
53        assert_eq!(
54            &totient_table(69)[1..],
55            vec![
56                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,
57                12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22,
58                46, 16, 42, 20, 32, 24, 52, 18, 40, 24, 36, 28, 58, 16, 60, 30, 36, 32, 48, 20, 66,
59                32, 44
60            ]
61            .as_slice()
62        );
63    }
64}
haar_lib/math/totient.rs

haar_lib/math/
totient.rs
