1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

use num_bigint::BigUint;
use num_traits::Zero;

/// Computes the greatest common divisor (GCD) of two `BigUint` numbers using the Euclidean algorithm.
///
/// The function applies the Euclidean algorithm to find the largest number that divides both `a` and `b`
/// without leaving a remainder. This algorithm involves a series of division steps until the remainder is zero.
///
/// # Arguments
///
/// * `a` - A reference to a `BigUint` representing the first number.
/// * `b` - A reference to a `BigUint` representing the second number.
///
/// # Returns
///
/// The greatest common divisor of `a` and `b`.
///
/// # Examples
///
/// ```
/// use num_bigint::BigUint;
/// let a = BigUint::from(60u32);
/// let b = BigUint::from(48u32);
/// let gcd_value = gcd(&a, &b);
/// assert_eq!(gcd_value, BigUint::from(12u32));
/// ```
pub fn gcd(a: &BigUint, b: &BigUint) -> BigUint {
    // Euclidean algorithm
    let mut a = a.clone();
    let mut b = b.clone();

    let zero = BigUint::zero();

    while b > zero {
        let temp = b.clone();
        b = a % b;
        a = temp;
    }

    return a;
}

#[cfg(test)]
mod tests {
    use num_bigint::BigUint;
    use num_traits::{ One, Zero };

    use super::*;

    #[test]
    fn edge_cases() {
        // Test case 0: 0
        assert_eq!(gcd(&BigUint::zero(), &BigUint::zero()), BigUint::zero());

        // Test case 1: 1
        assert_eq!(gcd(&BigUint::one(), &BigUint::zero()), BigUint::one());

        // Test case 2: 1
        assert_eq!(gcd(&BigUint::zero(), &BigUint::one()), BigUint::one());

        // Test case 3: 2
        assert_eq!(gcd(&BigUint::from(2u32), &BigUint::from(2u32)), BigUint::from(2u32));

        // Test case 4: 1
        assert_eq!(gcd(&BigUint::from(2u32), &BigUint::from(3u32)), BigUint::one());

        // Test case 5: 2
        assert_eq!(gcd(&BigUint::from(2u32), &BigUint::from(4u32)), BigUint::from(2u32));

        // Test case 6: 1
        assert_eq!(gcd(&BigUint::from(3u32), &BigUint::from(5u32)), BigUint::one());

        // Test case 7: 3
        assert_eq!(gcd(&BigUint::from(3u32), &BigUint::from(6u32)), BigUint::from(3u32));

        // Test case 8: 1
        assert_eq!(gcd(&BigUint::from(4u32), &BigUint::from(7u32)), BigUint::one());

        // Test case 9: 4
        assert_eq!(gcd(&BigUint::from(4u32), &BigUint::from(8u32)), BigUint::from(4u32));

        // Test case 10: 1
        assert_eq!(gcd(&BigUint::from(5u32), &BigUint::from(9u32)), BigUint::one());

        // Test case 11: 5
        assert_eq!(gcd(&BigUint::from(5u32), &BigUint::from(10u32)), BigUint::from(5u32));
    }

    #[test]
    fn general_cases() {
        // Big Numbers 6-8 digits

        assert_eq!(
            gcd(&BigUint::from(123456u32), &BigUint::from(123456u32)),
            BigUint::from(123456u32)
        );
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123457u32)), BigUint::one());
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123458u32)), BigUint::from(2u32));
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123459u32)), BigUint::from(3u32));
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123460u32)), BigUint::from(4u32));
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123461u32)), BigUint::one());
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123462u32)), BigUint::from(6u32));
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123463u32)), BigUint::one());
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123464u32)), BigUint::from(8u32));
        assert_eq!(gcd(&BigUint::from(123456u32), &BigUint::from(123465u32)), BigUint::from(3u32));
    }
}