最大公约数

  1. /// Greatest Common Divisor.
  2. ///
  3. /// greatest_common_divisor(num1, num2) returns the greatest number of num1 and num2.
  4. ///
  5. /// Wikipedia reference: https://en.wikipedia.org/wiki/Greatest_common_divisor
  6. /// gcd(a, b) = gcd(a, -b) = gcd(-a, b) = gcd(-a, -b) by definition of divisibility
  8. pub fn greatest_common_divisor_recursive(a: i64, b: i64) -> i64 {
  9.     if a == 0 {
  10.         b.abs()
  11.     } else {
  12.         greatest_common_divisor_recursive(b % a, a)
  13.     }
  14. }
  16. pub fn greatest_common_divisor_iterative(mut a: i64, mut b: i64) -> i64 {
  17.     while a != 0 {
  18.         let remainder = b % a;
  19.         b = a;
  20.         a = remainder;
  21.     }
  22.     b.abs()
  23. }
  25. #[cfg(test)]
  26. mod tests {
  27.     use super::*;
  29.     #[test]
  30.     fn positive_number_recursive() {
  31.         assert_eq!(greatest_common_divisor_recursive(4, 16), 4);
  32.         assert_eq!(greatest_common_divisor_recursive(16, 4), 4);
  33.         assert_eq!(greatest_common_divisor_recursive(3, 5), 1);
  34.         assert_eq!(greatest_common_divisor_recursive(40, 40), 40);
  35.         assert_eq!(greatest_common_divisor_recursive(27, 12), 3);
  36.     }
  38.     #[test]
  39.     fn positive_number_iterative() {
  40.         assert_eq!(greatest_common_divisor_iterative(4, 16), 4);
  41.         assert_eq!(greatest_common_divisor_iterative(16, 4), 4);
  42.         assert_eq!(greatest_common_divisor_iterative(3, 5), 1);
  43.         assert_eq!(greatest_common_divisor_iterative(40, 40), 40);
  44.         assert_eq!(greatest_common_divisor_iterative(27, 12), 3);
  45.     }
  47.     #[test]
  48.     fn negative_number_recursive() {
  49.         assert_eq!(greatest_common_divisor_recursive(-32, -8), 8);
  50.         assert_eq!(greatest_common_divisor_recursive(-8, -32), 8);
  51.         assert_eq!(greatest_common_divisor_recursive(-3, -5), 1);
  52.         assert_eq!(greatest_common_divisor_recursive(-40, -40), 40);
  53.         assert_eq!(greatest_common_divisor_recursive(-12, -27), 3);
  54.     }
  56.     #[test]
  57.     fn negative_number_iterative() {
  58.         assert_eq!(greatest_common_divisor_iterative(-32, -8), 8);
  59.         assert_eq!(greatest_common_divisor_iterative(-8, -32), 8);
  60.         assert_eq!(greatest_common_divisor_iterative(-3, -5), 1);
  61.         assert_eq!(greatest_common_divisor_iterative(-40, -40), 40);
  62.         assert_eq!(greatest_common_divisor_iterative(-12, -27), 3);
  63.     }
  65.     #[test]
  66.     fn mix_recursive() {
  67.         assert_eq!(greatest_common_divisor_recursive(0, -5), 5);
  68.         assert_eq!(greatest_common_divisor_recursive(-5, 0), 5);
  69.         assert_eq!(greatest_common_divisor_recursive(-64, 32), 32);
  70.         assert_eq!(greatest_common_divisor_recursive(-32, 64), 32);
  71.         assert_eq!(greatest_common_divisor_recursive(-40, 40), 40);
  72.         assert_eq!(greatest_common_divisor_recursive(12, -27), 3);
  73.     }
  75.     #[test]
  76.     fn mix_iterative() {
  77.         assert_eq!(greatest_common_divisor_iterative(0, -5), 5);
  78.         assert_eq!(greatest_common_divisor_iterative(-5, 0), 5);
  79.         assert_eq!(greatest_common_divisor_iterative(-64, 32), 32);
  80.         assert_eq!(greatest_common_divisor_iterative(-32, 64), 32);
  81.         assert_eq!(greatest_common_divisor_iterative(-40, 40), 40);
  82.         assert_eq!(greatest_common_divisor_iterative(12, -27), 3);
  83.     }
  84. }