自然数/整数 - 関数 - GCD

概要

2つの自然数/整数の最大公約数 (Greatest Common Divisor; GCD) を求める.

\[\gcd(a, b) = \begin{cases} a & \text{ if } b = 0 \\ \gcd(b, a \bmod b) & \text{ otherwise }\end{cases}\]

実装

/// Number - GCD on Natural Numbers
pub fn gcd(a: i128, b: i128) -> i128 {
    let a = a.abs();
    let b = b.abs();
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

#[cfg(test)]
mod test_gcd {
    use crate::num::gcd::*;

    #[test]
    fn it_works() {
        assert_eq!(gcd(10, 15), 5);
        assert_eq!(gcd(-10, 15), 5);
        assert_eq!(gcd(10, -15), 5);
        assert_eq!(gcd(-10, -15), 5);
        assert_eq!(gcd(-5, 0), 5);
    }
}