dsa/algorithms/intro_algorithm.rs
1/// Performs the Euclidean Algorithm on `a` and `b` to
2/// calculate the greatest common divisor (GCD) between
3/// `a` and `b`
4///
5/// # Parameters
6/// - `a`: An unsigned 64-bit integer
7/// - `b`: An unsigned 64-bit integer
8///
9/// # Returns
10/// - An unsigned 64-bit integer representing
11/// the greatest common divisor of `a` and `b`
12///
13/// # Examples
14/// ```
15/// use dsa::algorithms::intro_algorithm::euclidean_algorithm;
16///
17/// assert_eq!(euclidean_algorithm(20, 5), 5);
18/// ```
19pub fn euclidean_algorithm(mut a: u64, mut b: u64) -> u64 {
20 while b != 0 {
21 let temp = b;
22 b = a % b;
23 a = temp;
24 }
25
26 a
27}
28
29/// Performs the Euclidean Algorithm **recursively** on `a` and `b`
30/// to calculate the greatest common divisor (GCD) between
31/// `a` and `b`
32///
33/// # Parameters
34/// - `a`: An unsigned 64-bit integer
35/// - `b`: An unsigned 64-bit integer
36///
37/// # Returns
38/// - An unsigned 64-bit integer representing the
39/// greatest common divisor of `a` and `b`
40///
41/// # Examples
42/// ```
43/// use dsa::algorithms::intro_algorithm::euclidean_algorithm_recursion;
44///
45/// assert_eq!(euclidean_algorithm_recursion(20, 5), 5);
46/// ```
47pub fn euclidean_algorithm_recursion(a: u64, b: u64) -> u64 {
48 if b == 0 {
49 return a;
50 }
51
52 euclidean_algorithm_recursion(b, a % b)
53}