haar_lib/math/
divisor.rs

1//! 約数列挙
2
3/// 約数の個数を数える
4///
5/// **Time complexity** $O(\sqrt{n})$
6pub fn count_divisors(n: u64) -> u64 {
7    let mut ret = 0;
8
9    let mut i = 1;
10    while i * i <= n {
11        if n % i == 0 {
12            ret += 2;
13            if i * i == n {
14                ret -= 1;
15            }
16        }
17
18        i += 1;
19    }
20
21    ret
22}
23
24/// 約数を列挙する
25///
26/// **Time complexity** $O(\sqrt{n})$
27pub fn enumerate_divisors(n: u64) -> Vec<u64> {
28    let mut ret = vec![];
29    let mut temp = vec![];
30
31    let mut i = 1;
32    while i * i < n {
33        if n % i == 0 {
34            temp.push(n / i);
35            ret.push(i);
36        }
37
38        i += 1;
39    }
40
41    if i * i == n {
42        ret.push(i);
43    }
44
45    temp.reverse();
46    ret.extend(temp);
47
48    ret
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54
55    #[test]
56    fn test() {
57        let n = 24;
58        assert_eq!(
59            enumerate_divisors(n),
60            (1..=n).filter(|i| n % i == 0).collect::<Vec<_>>()
61        );
62    }
63}
haar_lib/math/divisor.rs

haar_lib/math/
divisor.rs
