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
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115

//! # divisors
//!
//! divisors is a blazing fast library to get all divisors of a natural number.

extern crate num;

use num::{Unsigned, NumCast, PrimInt};
use std::fmt::Display;

pub trait Num: NumCast + Unsigned + Copy + PrimInt + Display {}

impl Num for u8 {}
impl Num for u16 {}
impl Num for u32 {}
impl Num for u64 {}
impl Num for u128 {}
impl Num for usize {}

/// Return a vector with all divisors ordered of n in range (1, n-1).
///
/// # Example
///
/// ```
/// use std::time::{Instant};
///
/// fn main() {
///     let n: u128 = 934832147123321;
///     println!("finding divisors of {}", n);
///     let start_time = Instant::now();
///     let v = divisors::get_divisors(n);
///     println!("time = {:?}, divisors = {:?}", start_time.elapsed(), v);
/// }
/// ```
pub fn get_divisors<T: Num>(n: T) -> Vec<T> {
    
    let _0: T = T::zero();
    let _1: T = T::one();
    let _2: T = T::from(2).unwrap();
    let mut _n = n;
    let mut v: Vec<T> = Vec::new();
    
    let mut count_divisors_2: usize = 0;
    while _n & _1 == _0 {
        v.push(_2 << count_divisors_2);
        count_divisors_2 += 1;
        _n = _n >> 1;
    }
    
    let mut _x: T = T::from(3).unwrap();
    let mut _n_sqrt: T = approximated_sqrt(_n);
    while _x < _n_sqrt {        
        let mut _pow_x = _x;
        let v_len = v.len();
        let mut x_is_a_divisors = false;

        let mut pow_x_is_a_divisors = _n % _x == _0;
        while pow_x_is_a_divisors == true {
            _n = _n.div(_x);
            v.push(_pow_x);
            push_new_divisors(&mut v, v_len, _pow_x);
            pow_x_is_a_divisors = _n % _x == _0;
            if pow_x_is_a_divisors == true {
                _pow_x = _pow_x.mul(_x);                
            }
            x_is_a_divisors = true;
        }
        _x = _x + _2;
        if x_is_a_divisors == true {
            _n_sqrt = approximated_sqrt(_n);
        }
    }
    
    if _n > _1 && _n != n {
        let v_len = v.len();
        v.push(_n);
        push_new_divisors(&mut v, v_len, _n);
    }

    if v.len() > 1 {
        v.sort();
        v.pop();
    }
    
    v
}

/// Return a number near and greather then sqrt(n).
///
/// # Example
///
/// ```
/// fn main() {
///     let n: u32 = 63;
///     let n_sqrt  = divisors::approximated_sqrt(n);
///     assert_eq!(n_sqrt, 8);
/// }
/// ```
pub fn approximated_sqrt<T: Num>(n: T) -> T {
    let _0: T = T::zero();
    let _1: T = T::one();
    let mut num_bits = (std::mem::size_of::<T>() << 3) - 1;
    while ((n >> num_bits) & _1) == _0 {
        num_bits -= 1;
    }
    
    _1 << ((num_bits >> 1) + 1)
}


/// Iterate on v from 0 to v_len and for each element e: push (e * _x) in v.
fn push_new_divisors<T: Num>(v: &mut Vec<T>, v_len: usize, _x: T) {
    for i in 0..v_len {
        v.push(_x.mul(unsafe { *v.get_unchecked(i) }));
    }
}