algorithms_edu/algo/math/
gcd.rs

1use num_traits::{PrimInt, Signed, Unsigned};
2
3pub trait Gcd: PrimInt + Signed {
4    fn gcd(self, other: Self) -> Self {
5        if other == Self::zero() {
6            self.abs()
7        } else {
8            other.gcd(self % other)
9        }
10    }
11}
12
13pub trait GcdUnsigned: PrimInt + Unsigned {
14    fn gcd(self, other: Self) -> Self {
15        if other == Self::zero() {
16            self
17        } else {
18            other.gcd(self % other)
19        }
20    }
21}
22
23impl<I: Signed + PrimInt> Gcd for I {}
24
25impl<I: Unsigned + PrimInt> GcdUnsigned for I {}
26
27#[cfg(test)]
28mod tests {
29    use super::*;
30    #[test]
31    fn test_gcd() {
32        assert_eq!(12i32.gcd(18), 6);
33        assert_eq!((-12i32).gcd(18), 6);
34        assert_eq!(12i32.gcd(-18), 6);
35        assert_eq!((-12i32).gcd(-18), 6);
36        assert_eq!((5i32).gcd(0), 5);
37        assert_eq!((0i32).gcd(5), 5);
38        assert_eq!((-5i32).gcd(0), 5);
39        assert_eq!((0i32).gcd(-5), 5);
40        assert_eq!((0i32).gcd(0), 0);
41
42        assert_eq!(12u32.gcd(18), 6);
43        assert_eq!(12u128.gcd(18), 6);
44        assert_eq!(12i128.gcd(18), 6);
45    }
46}
algorithms_edu/algo/math/gcd.rs

algorithms_edu/algo/math/
gcd.rs
