binary_polynomial_mod_algebra 0.0.3

Basic algebra on univariate binary polynomial
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

use std::collections::HashSet;
use num_integer::Integer;

pub(super) fn prime_factors(num: usize) -> HashSet<usize> {
    let mut factors = HashSet::new();
    if num == 0 {
        return factors;
    }
    let mut n = num;
    if n.is_even() {
        factors.insert(2);
        n >>= n.trailing_zeros() as usize;
    }

    let mut i = 3usize;
    while i*i <= n {
        while n % i == 0 {
            factors.insert(i);
            n /= i;
        }
        i += 2;
    }
    if n > 2 {
        factors.insert(n);
    }
    factors
}

#[cfg(test)]
mod tests {
    use std::collections::HashSet;
    use crate::utils::prime_factors;

    #[test]
    fn test_prime_factors() {
        assert_eq!(prime_factors(0), HashSet::from([]));
        assert_eq!(prime_factors(1), HashSet::from([]));
        assert_eq!(prime_factors(7), HashSet::from([7]));
        assert_eq!(prime_factors(10), HashSet::from([5, 2]));
    }
}