math_utils/
lib.rs

1/// Finds the greatest common divisor
2///
3/// # Examples
4///
5/// ```
6/// let a = 10;
7/// let b = 15;
8///
9/// assert_eq!(math_utils::gcd(a, b), 5);
10/// ```
11///
12pub fn gcd(mut a: u64, mut b: u64) -> u64 {
13    assert!(a != 0 && b != 0);
14
15    while b != 0 {
16        if b < a {
17            let t = b;
18            b = a;
19            a = t;
20        }
21
22        b = b % a;
23    }
24    a
25}
26
27#[cfg(test)]
28mod tests {
29    use ::*;
30    #[test]
31    fn test_gdc() {
32        assert_eq!(gcd(14, 15), 1);
33
34        assert_eq!(gcd(2 * 3 * 5 * 11 * 17, 3 * 7 * 11 * 13 * 19), 3 * 11);
35    }
36}