069 Intermediate

069 — Sieve of Eratosthenes

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "069 — Sieve of Eratosthenes" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. The Sieve of Eratosthenes (circa 240 BC) is one of the oldest known algorithms, described by the Greek mathematician Eratosthenes of Cyrene. Key difference from OCaml: 1. **Functional vs imperative complexity**: The functional sieve is O(n² / log n) because each element is checked against every prime up to the square root. The boolean

Tutorial

The Problem

The Sieve of Eratosthenes (circa 240 BC) is one of the oldest known algorithms, described by the Greek mathematician Eratosthenes of Cyrene. The algorithm starts with all integers from 2 to n and repeatedly marks the multiples of each prime as composite. The unmarked numbers that remain are exactly the primes. This produces all primes up to n in a single pass.

Primes are foundational in modern computing: RSA encryption relies on the difficulty of factoring large primes, Diffie-Hellman key exchange works modulo prime numbers, hash table sizes are often chosen as primes to minimize collisions, and pseudo-random number generators use prime moduli. Generating primes efficiently is therefore not merely an academic exercise.

The naive functional version — recursively filter multiples — is elegant and short but runs in O(n² / log n) time. The imperative boolean-array sieve achieves O(n log log n), which grows extremely slowly. This example shows both and explains when each is appropriate.

🎯 Learning Outcomes

• Implement the functional sieve: filter out multiples of each head element recursively

• Implement the imperative sieve: a boolean array that marks composites in-place

• Understand the O(n log log n) vs O(n² / log n) complexity difference and what drives it

• Recognize the functional version as elegant but impractical for large n due to repeated filtering

• Use std::iter::from_fn or successors for lazy prime generation without upfront allocation

• Understand why the sieve is much faster than trial division for generating all primes up to n

Code Example

#![allow(clippy::all)]
/// 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.is_multiple_of(p)) {
            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]);
    }
}

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."

Key Differences

Functional vs imperative complexity: The functional sieve is O(n² / log n) because each element is checked against every prime up to the square root. The boolean-array sieve is O(n log log n) because each composite is marked at most once per prime factor.

Memory allocation: The functional version allocates a new Vec at each recursion level. The imperative version allocates exactly one boolean array and modifies it in place. At n = 10,000, the functional version performs thousands of allocations.

**retain vs filter**: Rust's Vec::retain(|x| x % p != 0) mutates in place. filter creates a new Vec. For the functional sieve style, filter is semantically cleaner; for the imperative style, in-place mutation is preferred.

Laziness: Rust's (2..).filter(|&n| is_prime(n)) with trial division is a lazy infinite iterator. Both the functional and imperative sieves are eager. Lazy sieves require more complex state management.

Stack overflow: The functional version recurses once per prime up to n. For large n, Rust's default stack size will overflow before OCaml (which uses continuations). The imperative version is iterative and stack-safe.

OCaml Approach

OCaml's functional sieve uses list pattern matching directly:

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

The seed list List.init (n - 1) (fun i -> i + 2) gives [2; 3; ...; n]. Each recursive call applies one more filter. OCaml has no built-in sieve in its standard library, so this manual implementation is standard in functional programming courses.

Full Source

#![allow(clippy::all)]
/// 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.is_multiple_of(p)) {
            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]);
    }
}

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."

✓ Tests Rust test suite

#[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]);
    }
}

Deep 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

Exercises

Segmented sieve: For large n (up to 10^9), a single boolean array is impractical. Implement a segmented sieve that computes primes in cache-sized blocks (e.g., 2^20 elements), using precomputed small primes to mark composites in each segment.

Prime factorization: Given the primes from the sieve, write factorize(n: u64, primes: &[u64]) -> Vec<u64> that returns the prime factorization of n by trial division using the known primes as candidates. This is much faster than naive trial division.

Goldbach verification: Goldbach's conjecture states every even integer > 2 is the sum of two primes. Write a function that verifies this for all even numbers up to n using the sieve output, finding the prime pair for each.

Open Source Repos

functional-rust

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

Rust

Tutorial Video

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

Sieve of Eratosthenes (Functional): OCaml vs Rust

The Core Insight

OCaml Approach

Rust Approach

Side-by-Side

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos