factors.rs
View source code here on GitHub!
Includes
- pub fn factors::proper_divisors<I>() -> ProperDivisors<I> where I: Hash + One + Zero + Add + Div + Rem + Mul
A convenience method that returns an iterator over the prime numbers.
1use std::collections::HashSet;
2use std::cmp::Ord;
3use std::hash::Hash;
4use std::ops::{Add,Div,Mul,Rem};
5
6use num_traits::{one,One,Zero};
7use itertools::Itertools;
8
9use crate::include::primes::prime_factors;
10
11#[derive(Clone, Debug)]
12pub struct ProperDivisors<I>
13{
14 seen: HashSet<I>,
15 factors: Vec<I>,
16 current_batch: Vec<I>,
17 curr_index: usize,
18 next_size: usize,
19}
20
21pub fn proper_divisors<I>(num: I) -> impl Iterator<Item = I>
22where I: Hash + Zero + One + Add + Ord + Copy + Div<Output=I> + Rem<Output=I> + Send + 'static
23{
24 return ProperDivisors::<I>::new(num);
25}
26
27impl<I> ProperDivisors<I>
28where I: Hash + Zero + One + Add + Ord + Copy + Div<Output=I> + Rem<Output=I> + Send + 'static
29{
30 pub fn new(num: I) -> Self {
31 return ProperDivisors::<I>{
32 seen: HashSet::new(),
33 factors: prime_factors(num).collect(),
34 current_batch: vec![],
35 curr_index: 0,
36 next_size: 0,
37 };
38 }
39}
40
41impl<I> Iterator for ProperDivisors<I>
42where I: Hash + Zero + One + Add + Ord + Copy + Div<Output=I> + Rem<Output=I> + Mul<Output=I>
43{
44 type Item = I;
45
46 fn next(&mut self) -> Option<Self::Item> {
47 loop {
48 if self.next_size > self.factors.len() {
49 return None;
50 }
51 if self.next_size == 0 {
52 self.next_size += 1;
53 return Some(one());
54 }
55 while self.curr_index < self.current_batch.len() {
56 let result = self.current_batch[self.curr_index];
57 self.curr_index += 1;
58 if !self.seen.contains(&result) {
59 self.seen.insert(result);
60 return Some(result);
61 }
62 }
63 self.current_batch = self.factors
64 .iter()
65 .cloned()
66 .combinations(self.next_size)
67 .map(|v| v.into_iter().fold(one(), |x, y| x * y))
68 .collect();
69 self.next_size += 1;
70 self.curr_index = 0;
71 }
72 }
73}