最大公约数

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. }