Prime Factorization

Overview

Decompose integers into their prime factors using recursive trial division. Optimized to extract factors of 2 first, then only check odd divisors — nearly halving the work for large inputs.

The Algorithm

let factors n =
  if n < 2 then invalid_arg "factors: input must be >= 2"
  else
    let rec extract_twos n =
      if n mod 2 = 0 then 2 :: extract_twos (n / 2)
      else odd_factors 3 n
    and odd_factors d n =
      if n = 1 then []
      else if d * d > n then [n]  (* n is prime *)
      else if n mod d = 0 then d :: odd_factors d (n / d)
      else odd_factors (d + 2) n  (* skip even candidates *)
    in
    extract_twos n

Mutual Recursion

The let rec ... and ... syntax defines two functions that call each other: extract_twos handles the factor-of-2 phase, then hands off to odd_factors. This is a natural way to express multi-phase algorithms in OCaml.

Early Exit at vn

The check d * d > n means: if no divisor up to vn divides n, then n itself is prime. This avoids checking all numbers up to n.

Output

factors 2 = [2]
factors 12 = [2; 2; 3]
factors 30 = [2; 3; 5]
factors 97 = [97]
factors 360 = [2; 2; 2; 3; 3; 5]