k0i/
euclidean.rs

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
use std::ops::{Div, Mul, Rem};

pub trait Euclidean<T>
where
    T: Copy + Ord + Mul<Output = Self> + Div<Output = Self> + Rem<Output = Self> + Default,
    Self: std::marker::Sized,
{
    fn gcd(x: T, y: T) -> T;
    fn lcm(x: T, y: T) -> Self;
}

impl<T> Euclidean<T> for T
where
    T: Copy + Ord + Mul<Output = Self> + Div<Output = Self> + Rem<Output = Self> + Default,
    Self: std::marker::Sized,
{
    /// ```
    /// use k0i::euclidean::Euclidean;
    /// assert_eq!(Euclidean::gcd(24, 32),8);
    /// ```
    fn gcd(mut x: T, mut y: T) -> T {
        while x != T::default() {
            if x < y {
                std::mem::swap(&mut x, &mut y);
            }
            x = x % y;
        }
        y
    }
    /// Returns LCM (Least Common Dividor) of x and y
    /// ```
    /// use k0i::euclidean::Euclidean;
    /// assert_eq!(Euclidean::lcm(24,36), 72);
    /// ```
    fn lcm(x: T, y: T) -> T {
        let gcd = Self::gcd(x, y);
        x * y / gcd
    }
}