Tripos 2024 Paper 1 Question 2 — Worked Solution

Question: Prime number testing and fold functions.

(a) Trial division primality test [8 marks]

let is_prime n =
  if n < 2 then false
  else
    let rec try_div d =
      if d * d > n then true
      else if n mod d = 0 then false
      else try_div (d + 1)
    in
    try_div 2

Explanation: For n < 2, there are no primes (1 is not prime by definition). For n ≥ 2, we use trial division. The key insight: if n is composite, it has a divisor d with 2 ≤ d ≤ √n. Equivalently, if no divisor d satisfies d² ≤ n, then n is prime. We test d = 2, 3, 4, ... checking divisibility with n mod d. Using d * d > n avoids floating-point square roots while giving the same bound because d > √n is equivalent to d² > n.

The function terminates because d strictly increases each step. The worst case is when n is prime: we test all numbers up to √n, giving O(√n) time complexity. The space complexity is O(1) — this is iterative (tail-recursive) since the recursive call is the last operation. We could make this faster by only testing odd divisors after checking d = 2 (since even numbers > 2 can’t be prime divisors), but the question specifies checking p² ≤ n which is satisfied by this implementation.

(b)(i) fold_range [4 marks]

let rec fold_range a b f acc =
  if a > b then acc
  else fold_range (a + 1) b f (f a acc)

Explanation: fold_range a b f acc applies f n for each n from a to b inclusive, accumulating results. The base case: when a > b, the range is exhausted, return acc. Otherwise, apply f a acc and recurse on a+1. This is tail-recursive: the recursive call is the last operation (the result of fold_range is returned directly). The type is val fold_range : int -> int -> (int -> 'a -> 'a) -> 'a -> 'a. For the example fold_range 1 3 (+) 10:

• fold_range 1 3 (+) 10 → fold_range 2 3 (+) (10 + 1) → fold_range 2 3 (+) 11
• → fold_range 3 3 (+) (11 + 2) → fold_range 3 3 (+) 13
• → fold_range 4 3 (+) (13 + 3) → 16 ✓

Time: O(b - a + 1) — linear in the size of the range. Space: O(1) — tail-recursive.

(b)(ii) fold (list fold) [2 marks]

let rec fold f acc = function
  | [] -> acc
  | x :: xs -> fold f (f acc x) xs

Explanation: This is a left fold (sometimes called foldl). It processes list elements from left to right, accumulating the result. Like fold_range, this is tail-recursive. The type is val fold : ('a -> 'b -> 'a) -> 'a -> 'b list -> 'a. For example, fold (+) 0 [1; 2; 3] computes ((0 + 1) + 2) + 3 = 6.

(b)(iii) Complexity analysis [3 marks]

Time complexity: O(n) where n is the length of the list. Each element is processed exactly once, and f acc x is assumed to take O(1) time (or whatever time f takes, multiplied by n).

Space complexity: O(1) stack space. The function is tail-recursive: the recursive call fold f (f acc x) xs is in tail position — its result is returned directly with no further computation. The OCaml compiler can optimise this to reuse the same stack frame, so the recursion does not consume stack space proportional to the list length.

This contrasts with a non-tail-recursive fold (which would nest operations and use O(n) stack space). The tail-recursive version is suitable for processing long lists without risking stack overflow.

(c) all_primes [3 marks]

let all_primes a b =
  fold_range a b (fun n acc ->
    if is_prime n then n :: acc
    else acc
  ) []

Explanation: We use fold_range to iterate through integers from a to b. For each n, if is_prime n returns true, we cons n onto the accumulator. Since we’re folding from a to b, the primes appear in reverse order in the result list (because a is processed first and consed, then a+1 is consed on top, etc.). If ascending order is desired, we would fold from b down to a, or reverse the result.

Alternative (with List.rev for correct order):

let all_primes a b =
  List.rev (fold_range a b (fun n acc ->
    if is_prime n then n :: acc else acc
  ) [])

The type is: val all_primes : int -> int -> int list.

Time complexity: O((b-a) × √b) in the worst case — for each number in the range we run is_prime which takes O(√b) time. Since the maximum value is b, the primality test dominates. Space: O(π(b) - π(a)) for the result list (the number of primes in the range), plus O(1) stack space.