Last active
May 18, 2024 23:59
-
-
Save Rudxain/1536d9af778cb8d4387ea1b51087a929 to your computer and use it in GitHub Desktop.
"incomplete" generic impls of proper divisors, in Rust
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| use core::iter::successors; | |
| use num_integer::{Integer, Roots}; //0.1 | |
| pub fn divisors_fast<T: Integer + Roots + Clone>(x: &T) -> Vec<T> { | |
| let sq = x.sqrt(); | |
| let mut divs = Vec::new(); | |
| let n1 = T::one(); | |
| let mut i = n1.clone() + n1; | |
| while i <= sq { | |
| if x.is_multiple_of(&i) { | |
| divs.push(i.clone()); | |
| } | |
| i.inc(); | |
| } | |
| drop(i); | |
| for d in divs | |
| .clone() | |
| .into_iter() | |
| .rev() | |
| // if perfect square, then avoid dupe | |
| .skip(usize::from(sq.clone() * sq == *x)) | |
| { | |
| divs.push(x.clone() / d.clone()); | |
| } | |
| divs | |
| } | |
| pub fn divisors_iter<T>(x: &T) -> impl Iterator<Item = T> + '_ | |
| where | |
| T: Integer + Clone + 'static, | |
| { | |
| let n1 = T::one(); | |
| let n2 = n1.clone() + n1.clone(); | |
| let n3 = n1.clone() + n2.clone(); | |
| successors(if *x > n3 { Some(n2) } else { None }, move |i| { | |
| let i = i.clone() + n1.clone(); | |
| if i < *x { | |
| Some(i) | |
| } else { | |
| None | |
| } | |
| }) | |
| .filter(|i| x.is_multiple_of(i)) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment