competitive_library/algorithm/
prime.rs

1//! 試割
2
3use std::collections::HashMap;
4pub fn trial_division(mut n: i64) -> HashMap<i64, i64> {
5    let mut primes = HashMap::new();
6    let mut i = 2;
7
8    while i * i <= n {
9        while n % i == 0 {
10            n /= i;
11            primes.entry(i).and_modify(|e| *e += 1).or_insert(1);
12        }
13        i += 1;
14    }
15    if n > 1 {
16        primes.entry(n).and_modify(|e| *e += 1).or_insert(1);
17    }
18    primes
19}
20
21#[cfg(test)]
22mod tests {
23    use super::*;
24
25    #[test]
26    fn test_trial_division() {
27        assert!(trial_division(25).contains_key(&5));
28        assert!(trial_division(25).get(&5).unwrap() == &2);
29    }
30}