utils/
factorisation.rs

1//!
2//! factorisation.rs
3//!
4//! Created by Mitchell Nordine at 05:03AM on May 29, 2014.
5//!
6//!
7
8use num::PrimInt as Int;
9use super::modulo;
10
11/// Check if the queried value is a factor of num.
12#[inline]
13pub fn is_factor<I>(num: I, query: I) -> bool
14where I: Int {
15    modulo(num, query) == I::zero()
16}
17
18/// Check if any of the queried values are a factor of num.
19#[inline]
20pub fn are_any_factors<I>(num: I, queries: &[I]) -> bool
21where I: Int + Copy {
22    queries.iter().any(|query| is_factor(num, *query))
23}
24
25/// Check if all of the queried values are a factor of num.
26#[inline]
27pub fn are_all_factors<I>(num: I, queries: &[I]) -> bool
28where I: Int + Copy {
29    queries.iter().all(|query| is_factor(num, *query))
30}
31
32/// Is the number prime?
33#[inline]
34pub fn is_prime<I>(num: I) -> bool
35where I: Int + Copy {
36    match get_all_factors(num).len() {
37        1 | 2 => true,
38        _ => false
39    }
40}
41
42/// Return the lowest non-one factor.
43#[inline]
44pub fn lowest_non_one<I>(n: I) -> Option<I>
45where I: Int + Copy {
46    let one: I = I::one();
47    let mut i: I = one + one;
48    while i * i <= n {
49        if n % i == I::zero() {
50            if i > one { return Some(i) }
51            else if i * i != n {
52                let n_div_i = n / i;
53                if n_div_i > one { return Some(n_div_i) }
54            }
55        }
56        i = i + one;
57    }
58    None
59}
60
61/// Get all factors for 'n'.
62#[inline]
63pub fn get_all_factors<I>(n: I) -> Vec<I> where I: Int {
64    let one: I = I::one();
65    let mut factors: Vec<I> = vec![one];
66    let mut i: I = one + one;
67    while i * i <= n {
68        if n % i == I::zero() {
69            factors.push(i);
70            if i * i != n { factors.push(n / i); }
71        }
72        i = i + one;
73    }
74    factors.push(n);
75    factors.sort_by(|a, b| a.cmp(b));
76    return factors; 
77}
78
utils/factorisation.rs

utils/
factorisation.rs
