Example 069: Sieve of Eratosthenes (Functional)

Difficulty: ⭐⭐ Category: Algorithms Concept: A purely functional prime sieve using recursive filtering. Each prime eliminates its multiples from the remaining candidates. Shows the contrast between elegant functional style and efficient imperative implementation. OCaml → Rust insight: OCaml's recursive filter sieve is concise but O(n × primes); Rust naturally gravitates toward the boolean-array sieve (O(n log log n)) because mutable arrays are zero-cost.

/// Sieve of Eratosthenes (Functional)
///
/// A purely functional prime sieve using recursive filtering.
/// OCaml's version recursively filters a list. Rust's idiomatic
/// version uses a boolean array (imperative sieve) but we show
/// both functional and imperative approaches.

/// Functional sieve — recursive filter, mirrors the OCaml version.
/// Not efficient (O(n * primes) due to repeated filtering) but elegant.
pub fn sieve_functional(candidates: Vec<u64>) -> Vec<u64> {
    match candidates.as_slice() {
        [] => vec![],
        [p, ..] => {
            let p = *p;
            let rest: Vec<u64> = candidates[1..]
                .iter()
                .filter(|&&n| n % p != 0)
                .copied()
                .collect();
            let mut result = vec![p];
            result.extend(sieve_functional(rest));
            result
        }
    }
}

pub fn primes_up_to_functional(n: u64) -> Vec<u64> {
    if n < 2 {
        return vec![];
    }
    let candidates: Vec<u64> = (2..=n).collect();
    sieve_functional(candidates)
}

/// Imperative sieve — idiomatic Rust, O(n log log n).
pub fn primes_up_to(n: usize) -> Vec<usize> {
    if n < 2 {
        return vec![];
    }
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    is_prime[1] = false;

    let mut i = 2;
    while i * i <= n {
        if is_prime[i] {
            let mut j = i * i;
            while j <= n {
                is_prime[j] = false;
                j += i;
            }
        }
        i += 1;
    }

    (0..=n).filter(|&i| is_prime[i]).collect()
}

/// Iterator-based: generate primes lazily using trial division.
pub fn nth_prime(n: usize) -> u64 {
    let mut primes = Vec::new();
    let mut candidate = 2u64;
    while primes.len() < n {
        if primes.iter().all(|&p| candidate % p != 0) {
            primes.push(candidate);
        }
        candidate += 1;
    }
    *primes.last().unwrap()
}

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

    #[test]
    fn test_primes_up_to_50() {
        let expected = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47];
        assert_eq!(primes_up_to(50), expected);
    }

    #[test]
    fn test_functional_sieve() {
        let expected: Vec<u64> = vec![2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47];
        assert_eq!(primes_up_to_functional(50), expected);
    }

    #[test]
    fn test_count_up_to_100() {
        assert_eq!(primes_up_to(100).len(), 25);
    }

    #[test]
    fn test_nth_prime() {
        assert_eq!(nth_prime(10), 29);
    }

    #[test]
    fn test_edge_cases() {
        assert_eq!(primes_up_to(0), vec![]);
        assert_eq!(primes_up_to(1), vec![]);
        assert_eq!(primes_up_to(2), vec![2]);
    }

    #[test]
    fn test_small() {
        assert_eq!(primes_up_to(10), vec![2, 3, 5, 7]);
    }
}

fn main() {
    println!("{:?}", primes_up_to(50), expected);
    println!("{:?}", primes_up_to_functional(50), expected);
    println!("{:?}", primes_up_to(100).len(), 25);
}

let rec sieve = function
  | []      -> []
  | p :: rest ->
    p :: sieve (List.filter (fun n -> n mod p <> 0) rest)

let primes_up_to n =
  if n < 2 then []
  else sieve (List.init (n - 1) (fun i -> i + 2))

let () =
  let ps = primes_up_to 50 in
  assert (ps = [2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47]);
  assert (List.length (primes_up_to 100) = 25);
  print_endline "All assertions passed."

📊 Detailed Comparison

Sieve of Eratosthenes (Functional): OCaml vs Rust

The Core Insight

The prime sieve beautifully illustrates the elegance-vs-efficiency tradeoff. OCaml's recursive filter version is a gorgeous three-liner that reads like mathematics. Rust can replicate it, but the idiomatic approach is a mutable boolean array that's orders of magnitude faster — and Rust makes that mutation safe.

OCaml Approach

OCaml's `sieve` function is textbook elegance: take the first element as a prime, filter out its multiples, recurse on the rest. `List.filter (fun n -> n mod p <> 0) rest` does the heavy lifting. Each recursive call produces a new filtered list — the GC handles all the intermediate allocations. This isn't the true Sieve of Eratosthenes (it's trial division), but it captures the spirit beautifully.

Rust Approach

Rust offers both styles. The functional version uses `iter().filter().copied().collect()` to mirror OCaml's approach, but each step allocates a new Vec. The imperative sieve uses `vec![true; n+1]` as a boolean array, marking composites in-place — O(n log log n) with minimal allocation. Rust's ownership system ensures the mutable array can't be accessed from multiple threads accidentally, making the imperative version both safe and fast.

Side-by-Side

Concept	OCaml	Rust
Functional sieve	`p :: sieve (List.filter ...)`	`vec![p]; result.extend(sieve(...))`
Imperative sieve	Not idiomatic	`vec![true; n+1]` + mutation
Complexity	O(n × #primes)	O(n log log n) imperative
Memory	GC handles intermediate lists	Single boolean array
Style	Recursive filtering	Iterator or loop

What Rust Learners Should Notice

The functional sieve works in Rust but allocates a new Vec per prime — expensive compared to OCaml's GC-optimized list allocation
The imperative sieve in Rust is both idiomatic and performant — `vec![true; n]` is a single allocation
`iter().filter().copied().collect()` is Rust's equivalent of OCaml's `List.filter` — note `copied()` to go from `&u64` to `u64`
Rust lets you choose: functional elegance for small inputs, imperative efficiency for large ones — both are safe
This is a case where OCaml's style is more natural; Rust's strength is making the efficient version equally safe