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}