factors/
lib.rs

1pub trait Factors: Sized {
2    fn factors(self) -> impl Iterator<Item = ((Self, u32), Self)>;
3}
4
5pub trait FactorsDup: Sized {
6    fn factors_dup(self) -> impl Iterator<Item = Self>;
7}
8
9macro_rules! impl_uint {
10    ( $($ty:ty)* ) => { $(
11        impl Factors for $ty {
12            fn factors(self) -> impl Iterator<Item = ((Self, u32), Self)> {
13                let n = self;
14                std::iter::successors(
15                    (n >= 1).then_some((((1, 0), 1), n)),
16                    move |&(((i, _), _), n)| {
17                        if let Some(j) =
18                            (i + 1..).take_while(|j| j * j <= n).find(|j| n % j == 0)
19                        {
20                            let (jj, e) =
21                                std::iter::successors(Some((j, 1)), |&(jj, e)| {
22                                    (n / jj % j == 0).then(|| (jj * j, e + 1))
23                                })
24                                .last()
25                                .unwrap();
26                            Some((((j, e), jj), n / jj))
27                        } else if n > 1 {
28                            Some((((n, 1), n), 1))
29                        } else {
30                            None
31                        }
32                    },
33                )
34                .skip(1)
35                .map(move |(i, _)| i)
36            }
37        }
38
39        impl FactorsDup for $ty {
40            fn factors_dup(self) -> impl Iterator<Item = Self> {
41                let n = self;
42                std::iter::successors((n >= 1).then_some((1, n)), move |&(i, n)| {
43                    if let Some(j) =
44                        (i.max(2)..).take_while(|j| j * j <= n).find(|j| n % j == 0)
45                    {
46                        Some((j, n / j))
47                    } else if n > 1 {
48                        Some((n, 1))
49                    } else {
50                        None
51                    }
52                })
53                .skip(1)
54                .map(move |(i, _)| i)
55            }
56        }
57    )* };
58}
59
60impl_uint! { u8 u16 u32 u64 u128 usize }
61
62#[test]
63fn sanity_check() {
64    assert!(0_u32.factors_dup().eq(None));
65
66    let n_max = 10000;
67    let primes: Vec<_> = {
68        let mut is_prime = vec![true; n_max + 1];
69        is_prime[0] = false;
70        is_prime[1] = false;
71        for n in 2..=n_max {
72            for i in n..=n_max / n {
73                is_prime[i * n] = false;
74            }
75        }
76        (2..=n_max).filter(|&n| is_prime[n]).collect()
77    };
78    let expected = {
79        let mut res = vec![vec![]; n_max + 1];
80        for n in 2..=n_max {
81            let mut n_ = n;
82            for &p in &primes {
83                while n_ % p == 0 {
84                    n_ /= p;
85                    res[n].push(p);
86                }
87            }
88        }
89        res
90    };
91
92    for n in 1..=n_max {
93        let actual = n.factors_dup();
94        assert!(actual.eq(expected[n].iter().copied()));
95
96        let expected_dedup = {
97            let mut tmp: Vec<_> = n.factors_dup().collect();
98            tmp.dedup();
99            tmp
100        };
101        let actual_dedup = n.factors().map(|((p, _), _)| p);
102        assert!(actual_dedup.eq(expected_dedup));
103
104        for ((p, e), pp) in n.factors() {
105            assert_eq!(n / (pp / p) % p, 0);
106            assert_ne!(n / pp % p, 0);
107            assert_eq!(pp, p.pow(e));
108        }
109    }
110}
factors/lib.rs

factors/
lib.rs
