071: GCD and LCM

Difficulty: Beginner Category: Mathematics Concept: Greatest Common Divisor (Euclidean algorithm) and Least Common Multiple Key Insight: GCD is naturally recursive; LCM = a*b/gcd(a,b). Both languages express this identically.

// 071: GCD and LCM

// Approach 1: Recursive GCD (Euclidean)
fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 { a.abs() } else { gcd(b, a % b) }
}

fn lcm(a: i64, b: i64) -> i64 {
    if a == 0 || b == 0 { 0 } else { (a * b).abs() / gcd(a, b) }
}

// Approach 2: Iterative GCD
fn gcd_iter(mut a: i64, mut b: i64) -> i64 {
    a = a.abs();
    b = b.abs();
    while b != 0 {
        let t = b;
        b = a % b;
        a = t;
    }
    a
}

// GCD/LCM of a slice
fn gcd_list(v: &[i64]) -> i64 {
    v.iter().copied().reduce(gcd).unwrap_or(0)
}

fn lcm_list(v: &[i64]) -> i64 {
    v.iter().copied().reduce(lcm).unwrap_or(1)
}

// Approach 3: Extended GCD
fn extended_gcd(a: i64, b: i64) -> (i64, i64, i64) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (g, x, y) = extended_gcd(b, a % b);
        (g, y, x - (a / b) * y)
    }
}

fn main() {
    println!("gcd(12, 8) = {}", gcd(12, 8));
    println!("lcm(4, 6) = {}", lcm(4, 6));
    println!("gcd_list([12,18,24]) = {}", gcd_list(&[12, 18, 24]));
    println!("lcm_list([4,6,8]) = {}", lcm_list(&[4, 6, 8]));
    let (g, x, y) = extended_gcd(35, 15);
    println!("extended_gcd(35,15) = ({}, {}, {})", g, x, y);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_gcd() {
        assert_eq!(gcd(12, 8), 4);
        assert_eq!(gcd(17, 5), 1);
        assert_eq!(gcd(0, 5), 5);
        assert_eq!(gcd(100, 0), 100);
    }

    #[test]
    fn test_lcm() {
        assert_eq!(lcm(4, 6), 12);
        assert_eq!(lcm(3, 5), 15);
        assert_eq!(lcm(0, 5), 0);
    }

    #[test]
    fn test_gcd_iter() {
        assert_eq!(gcd_iter(12, 8), 4);
        assert_eq!(gcd_iter(-12, 8), 4);
    }

    #[test]
    fn test_list_ops() {
        assert_eq!(gcd_list(&[12, 18, 24]), 6);
        assert_eq!(lcm_list(&[4, 6, 8]), 24);
    }

    #[test]
    fn test_extended_gcd() {
        let (g, x, y) = extended_gcd(35, 15);
        assert_eq!(g, 5);
        assert_eq!(35 * x + 15 * y, 5);
    }
}

(* 071: GCD and LCM *)

(* Approach 1: Recursive GCD *)
let rec gcd a b =
  if b = 0 then abs a
  else gcd b (a mod b)

let lcm a b =
  if a = 0 || b = 0 then 0
  else abs (a * b) / gcd a b

(* Approach 2: GCD of a list *)
let gcd_list = function
  | [] -> 0
  | x :: xs -> List.fold_left gcd x xs

let lcm_list = function
  | [] -> 1
  | x :: xs -> List.fold_left lcm x xs

(* Approach 3: Extended GCD — returns (g, x, y) where ax + by = g *)
let rec extended_gcd a b =
  if b = 0 then (a, 1, 0)
  else
    let g, x, y = extended_gcd b (a mod b) in
    (g, y, x - (a / b) * y)

(* Tests *)
let () =
  assert (gcd 12 8 = 4);
  assert (gcd 17 5 = 1);
  assert (gcd 0 5 = 5);
  assert (gcd 100 0 = 100);
  assert (lcm 4 6 = 12);
  assert (lcm 3 5 = 15);
  assert (lcm 0 5 = 0);
  assert (gcd_list [12; 18; 24] = 6);
  assert (lcm_list [4; 6; 8] = 24);
  let (g, x, y) = extended_gcd 35 15 in
  assert (g = 5);
  assert (35 * x + 15 * y = 5);
  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Core Insight

The Euclidean algorithm: `gcd(a, b) = gcd(b, a mod b)` with base case `gcd(a, 0) = a`. LCM derives from GCD. The recursive structure is identical in both languages.

OCaml Approach

Recursive function with pattern matching
Tail-recursive naturally (last call is recursive)
`abs` for handling negative inputs

Rust Approach

Recursive or iterative (loop with swap)
No guaranteed TCO but small depth for GCD
Can use `.abs()` method on integers

Comparison Table

Feature	OCaml	Rust
GCD	`let rec gcd a b = ...`	`fn gcd(a, b) -> ...`
Pattern	`match b with 0 -> a`	`if b == 0 { a }`
LCM	`a b / gcd a b`	`a b / gcd(a, b)`
Overflow	No (arbitrary precision with Zarith)	Possible with i32/i64