Skip to content

Instantly share code, notes, and snippets.

@Rudxain

Rudxain/divisors.rs

Last active May 18, 2024 23:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Rudxain/1536d9af778cb8d4387ea1b51087a929 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Rudxain/1536d9af778cb8d4387ea1b51087a929 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Rudxain revised this gist May 18, 2024. 1 changed file with 14 additions and 1 deletion.
    15 changes: 14 additions & 1 deletion divisors.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,5 @@
    #![warn(clippy::pedantic, clippy::nursery)]

    use core::iter::successors;
    use num_integer::{Integer, Roots}; //0.1

    @@ -6,11 +8,13 @@ pub fn divisors_fast<T: Integer + Roots + Clone>(x: &T) -> Vec<T> {
    let mut divs = Vec::new();

    let n1 = T::one();
    let mut i = n1.clone() + n1;
    let n2 = n1.clone() + n1;
    let mut i = n2;
    while i <= sq {
    if x.is_multiple_of(&i) {
    divs.push(i.clone());
    }
    // to-do: skip evens if x isn't even
    i.inc();
    }
    drop(i);
    @@ -45,3 +49,12 @@ where
    })
    .filter(|i| x.is_multiple_of(i))
    }

    fn main() {
    for i in 0..=u8::MAX {
    let f = divisors_fast(&i);
    let t: Vec<_> = divisors_iter(&i).collect();
    assert_eq!(f, t);
    println!("{f:?}");
    }
    }
  2. Rudxain revised this gist May 18, 2024. 1 changed file with 8 additions and 10 deletions.
    18 changes: 8 additions & 10 deletions divisors.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -1,23 +1,20 @@
    #![warn(clippy::pedantic, clippy::nursery)]

    use core::iter::successors;

    use num_integer::{Integer, Roots}; // 0.1
    use num_integer::{Integer, Roots}; //0.1

    pub fn divisors_fast<T: Integer + Roots + Clone>(x: &T) -> Vec<T> {
    let n1 = T::one();
    let n2 = n1.clone() + n1;

    let sq = x.sqrt();
    let mut divs = Vec::new();

    let mut i = n2;
    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()
    @@ -35,9 +32,10 @@ where
    T: Integer + Clone + 'static,
    {
    let n1 = T::one();
    let n2 = T::one() + T::one();
    let n2 = n1.clone() + n1.clone();
    let n3 = n1.clone() + n2.clone();

    successors(Some(n2), move |i| {
    successors(if *x > n3 { Some(n2) } else { None }, move |i| {
    let i = i.clone() + n1.clone();
    if i < *x {
    Some(i)
  3. Rudxain revised this gist May 18, 2024. No changes.
  4. Rudxain created this gist May 18, 2024.
    49 changes: 49 additions & 0 deletions divisors.rs
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,49 @@
    #![warn(clippy::pedantic, clippy::nursery)]

    use core::iter::successors;

    use num_integer::{Integer, Roots}; // 0.1

    pub fn divisors_fast<T: Integer + Roots + Clone>(x: &T) -> Vec<T> {
    let n1 = T::one();
    let n2 = n1.clone() + n1;

    let sq = x.sqrt();
    let mut divs = Vec::new();

    let mut i = n2;
    while i <= sq {
    if x.is_multiple_of(&i) {
    divs.push(i.clone());
    }
    i.inc();
    }
    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 = T::one() + T::one();

    successors(Some(n2), move |i| {
    let i = i.clone() + n1.clone();
    if i < *x {
    Some(i)
    } else {
    None
    }
    })
    .filter(|i| x.is_multiple_of(i))
    }