825 Intermediate

Prime Factorization

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Prime Factorization" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Decomposing an integer into its prime factors is fundamental to number theory: computing GCD, LCM, Euler's totient, cryptographic key generation, and combinatorial coefficient calculations all rely on factorization. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Decomposing an integer into its prime factors is fundamental to number theory: computing GCD, LCM, Euler's totient, cryptographic key generation, and combinatorial coefficient calculations all rely on factorization. For small numbers, trial division by primes up to sqrt(n) suffices. For large numbers (64-bit), Pollard's rho algorithm factorizes in O(n^(1/4)) expected time. Real-world cryptography relies on the hardness of factorizing large composites (RSA). Competitive programming uses factorization for: divisor enumeration, Mobius function, Euler's phi, and modular arithmetic.

🎯 Learning Outcomes

• Implement trial division factorization in O(sqrt(n)) by testing primes up to sqrt(n)

• Represent the factorization as a map from prime to exponent: HashMap<u64, u32>

• Apply factorization to compute number of divisors, sum of divisors, Euler's phi

• Understand when to use sieve-based factorization (many numbers up to N) vs. per-number trial division

• Recognize the smallest prime factor sieve for batch factorization in O(log n) per number

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Prime Factorization in OCaml — trial division + Pollard rho concept *)

(* GCD — the elegant one-liner *)
let rec gcd a b = if b = 0 then a else gcd b (a mod b)

(* Trial division factorization *)
let factorize (n : int) : (int * int) list =
  let factors = ref [] in
  let n = ref n in
  (* Handle factor 2 separately *)
  let cnt = ref 0 in
  while !n mod 2 = 0 do
    incr cnt; n := !n / 2
  done;
  if !cnt > 0 then factors := (2, !cnt) :: !factors;
  (* Odd factors from 3 to sqrt(n) *)
  let d = ref 3 in
  while !d * !d <= !n do
    cnt := 0;
    while !n mod !d = 0 do
      incr cnt; n := !n / !d
    done;
    if !cnt > 0 then factors := (!d, !cnt) :: !factors;
    d := !d + 2
  done;
  (* Remaining factor is prime *)
  if !n > 1 then factors := (!n, 1) :: !factors;
  List.rev !factors

(* Pollard's rho: find a non-trivial factor of n (n must be composite) *)
let pollard_rho (n : int) : int =
  if n mod 2 = 0 then 2
  else begin
    let x = ref 2 and y = ref 2 and c = ref 1 and d = ref 1 in
    while !d = 1 do
      x := (!x * !x + !c) mod n;
      y := (!y * !y + !c) mod n;
      y := (!y * !y + !c) mod n;
      d := gcd (abs (!x - !y)) n;
      if !d = n then begin
        (* Retry with different c *)
        c := !c + 1; x := 2; y := 2; d := 1
      end
    done;
    !d
  end

(* Pretty-print factorization *)
let pp_factors factors =
  String.concat " × " (List.map (fun (p, e) ->
    if e = 1 then string_of_int p
    else Printf.sprintf "%d^%d" p e
  ) factors)

let () =
  let tests = [12; 100; 360; 97; 1234567890; 720720] in
  List.iter (fun n ->
    let f = factorize n in
    Printf.printf "factorize(%d) = %s\n" n (pp_factors f)
  ) tests;
  (* Verify: product should equal n *)
  let n = 360 in
  let f = factorize n in
  let product = List.fold_left (fun acc (p, e) ->
    let rec pow b e = if e = 0 then 1 else b * pow b (e-1) in
    acc * pow p e
  ) 1 f in
  Printf.printf "product check: %d = %d → %b\n" n product (n = product)

Key Differences

Aspect	Rust	OCaml
Factor map	`HashMap<u64, u32>`	`Hashtbl` or `(int * int) list`
Mutation	Takes `mut n: u64` by value	`let n = ref n`
Entry update	`.entry().or_insert(0) += 1`	`Hashtbl.replace` or match
Large numbers	`u64` (max ~1.8 * 10^19)	`Zarith` for arbitrary precision
Sieve integration	Can import SPF sieve function	`Array.get spf n`
Remaining prime	`if n > 1` check after loop	Same pattern

OCaml Approach

OCaml uses a Hashtbl or returns a sorted (int * int) list of (prime, exponent) pairs. The recursive functional version divides out factors recursively, building the list with pattern matching. Trial division uses a while loop with mutable n ref. OCaml's Map.Make(Int) provides an immutable sorted factor map. The let () = while !n mod d = 0 do ... done pattern mirrors the Rust approach. For large numbers, OCaml's Zarith library handles arbitrary-precision factorization.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Prime Factorization in OCaml — trial division + Pollard rho concept *)

(* GCD — the elegant one-liner *)
let rec gcd a b = if b = 0 then a else gcd b (a mod b)

(* Trial division factorization *)
let factorize (n : int) : (int * int) list =
  let factors = ref [] in
  let n = ref n in
  (* Handle factor 2 separately *)
  let cnt = ref 0 in
  while !n mod 2 = 0 do
    incr cnt; n := !n / 2
  done;
  if !cnt > 0 then factors := (2, !cnt) :: !factors;
  (* Odd factors from 3 to sqrt(n) *)
  let d = ref 3 in
  while !d * !d <= !n do
    cnt := 0;
    while !n mod !d = 0 do
      incr cnt; n := !n / !d
    done;
    if !cnt > 0 then factors := (!d, !cnt) :: !factors;
    d := !d + 2
  done;
  (* Remaining factor is prime *)
  if !n > 1 then factors := (!n, 1) :: !factors;
  List.rev !factors

(* Pollard's rho: find a non-trivial factor of n (n must be composite) *)
let pollard_rho (n : int) : int =
  if n mod 2 = 0 then 2
  else begin
    let x = ref 2 and y = ref 2 and c = ref 1 and d = ref 1 in
    while !d = 1 do
      x := (!x * !x + !c) mod n;
      y := (!y * !y + !c) mod n;
      y := (!y * !y + !c) mod n;
      d := gcd (abs (!x - !y)) n;
      if !d = n then begin
        (* Retry with different c *)
        c := !c + 1; x := 2; y := 2; d := 1
      end
    done;
    !d
  end

(* Pretty-print factorization *)
let pp_factors factors =
  String.concat " × " (List.map (fun (p, e) ->
    if e = 1 then string_of_int p
    else Printf.sprintf "%d^%d" p e
  ) factors)

let () =
  let tests = [12; 100; 360; 97; 1234567890; 720720] in
  List.iter (fun n ->
    let f = factorize n in
    Printf.printf "factorize(%d) = %s\n" n (pp_factors f)
  ) tests;
  (* Verify: product should equal n *)
  let n = 360 in
  let f = factorize n in
  let product = List.fold_left (fun acc (p, e) ->
    let rec pow b e = if e = 0 then 1 else b * pow b (e-1) in
    acc * pow p e
  ) 1 f in
  Printf.printf "product check: %d = %d → %b\n" n product (n = product)

Deep Comparison

OCaml vs Rust: Prime Factorization

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Use factorization to compute the number of divisors of n: product of (exponent + 1) over all prime factors.

Implement Euler's totient phi(n) from the prime factorization: n * product of (1 - 1/p) for each prime p.

Compute LCM of a list of numbers using their prime factorizations (max exponent per prime).

Implement the smallest prime factor sieve and compare batch factorization speed vs. per-number trial division for 10^6 numbers.

Implement Pollard's rho algorithm for factorizing 64-bit numbers and measure speedup on large semiprimes.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust