```  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
```
```//! # divisors
//!
//! divisors is a blazing fast library to get all divisors of a natural number.

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) }));
}
}
```