competitive_library/algorithm/
enum_divisors.rs

1//!  約数列挙
2pub fn enum_divisors(n: i64) -> Vec<i64> {
3    let mut res = vec![];
4    for i in 1..=(n as f64).sqrt() as i64 {
5        if n % i != 0 {
6            continue;
7        }
8        res.push(i);
9        if i.pow(2) != n {
10            res.push(n / i);
11        }
12    }
13    res
14}
15
16#[cfg(test)]
17mod tests {
18    use super::*;
19    use std::collections::HashMap;
20
21    #[test]
22    fn test_enum_divisors() {
23        let map = {
24            let mut ret = HashMap::new();
25            ret.insert(0, vec![]);
26            ret.insert(1, vec![1]);
27            ret.insert(2, vec![1, 2]);
28            ret.insert(3, vec![1, 3]);
29            ret.insert(4, vec![1, 2, 4]);
30            ret.insert(6, vec![1, 2, 3, 6]);
31            ret.insert(20, vec![1, 2, 4, 5, 10, 20]);
32            ret.insert(25, vec![1, 5, 25]);
33            ret.insert(30, vec![1, 2, 3, 5, 6, 10, 15, 30]);
34            ret.insert(
35                2520,
36                vec![
37                    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 18, 20, 21, 24, 28, 30, 35, 36, 40,
38                    42, 45, 56, 60, 63, 70, 72, 84, 90, 105, 120, 126, 140, 168, 180, 210, 252,
39                    280, 315, 360, 420, 504, 630, 840, 1260, 2520,
40                ],
41            );
42            ret.insert(1_000_000_007, vec![1, 1_000_000_007]);
43            ret
44        };
45
46        for (k, v) in map {
47            let mut a = enum_divisors(k);
48            a.sort_unstable();
49            assert_eq!(a, v);
50        }
51    }
52}
competitive_library/algorithm/enum_divisors.rs

competitive_library/algorithm/
enum_divisors.rs
