824 Intermediate

Sieve of Eratosthenes

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Sieve of Eratosthenes" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. Generating all prime numbers up to N is a fundamental operation in number theory with applications in cryptography (RSA key generation requires large primes), competitive programming, and mathematical software. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Generating all prime numbers up to N is a fundamental operation in number theory with applications in cryptography (RSA key generation requires large primes), competitive programming, and mathematical software. Trial division for each number takes O(sqrt(n)) per number, giving O(n*sqrt(n)) total. The Sieve of Eratosthenes achieves O(n log log n) by marking multiples of each prime in bulk: once 2's multiples are marked, 3's multiples, 5's multiples, etc. Every composite number gets eliminated exactly once. For N up to 10^7, the sieve runs in milliseconds and uses O(n) memory. Segmented variants extend this to arbitrary ranges without holding all of 0..N in memory.

🎯 Learning Outcomes

• Implement the classic sieve: initialize all to true, mark multiples of each prime starting from p^2

• Understand why we start marking from p^2: smaller multiples were already marked by earlier primes

• Recognize the time complexity: each composite is marked exactly once by its smallest prime factor

• Learn the segmented sieve for memory-efficient prime generation for very large N

• Apply the sieve to number-theoretic computations: Euler's totient, smallest prime factor table

Code Example

#![allow(clippy::all)]
//! # Sieve of Eratosthenes
pub fn sieve(n: usize) -> Vec<bool> {
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    if n >= 1 {
        is_prime[1] = false;
    }
    for i in 2..=((n as f64).sqrt() as usize) {
        if is_prime[i] {
            for j in (i * i..=n).step_by(i) {
                is_prime[j] = false;
            }
        }
    }
    is_prime
}

pub fn primes_up_to(n: usize) -> Vec<usize> {
    sieve(n)
        .iter()
        .enumerate()
        .filter_map(|(i, &b)| if b { Some(i) } else { None })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_sieve() {
        assert_eq!(primes_up_to(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
    }
}

(* Sieve of Eratosthenes in OCaml *)

(* Return all primes up to and including limit *)
let sieve (limit : int) : int list =
  if limit < 2 then []
  else begin
    let is_prime = Array.make (limit + 1) true in
    is_prime.(0) <- false;
    is_prime.(1) <- false;
    let sqrt_limit = int_of_float (sqrt (float_of_int limit)) in
    for p = 2 to sqrt_limit do
      if is_prime.(p) then begin
        let j = ref (p * p) in
        while !j <= limit do
          is_prime.(!j) <- false;
          j := !j + p
        done
      end
    done;
    (* Collect all primes functionally *)
    Array.to_seq is_prime
    |> Seq.filter_mapi (fun i b -> if b then Some i else None)
    |> List.of_seq
  end

(* Count primes up to n (prime-counting function π(n)) *)
let prime_pi (n : int) : int =
  List.length (sieve n)

(* Segmented sieve for large ranges — sieve [lo, hi] *)
let segmented_sieve (lo : int) (hi : int) : int list =
  let base_primes = sieve (int_of_float (sqrt (float_of_int hi)) + 1) in
  let size = hi - lo + 1 in
  let is_prime = Array.make size true in
  (* 0 and 1 are not prime *)
  if lo <= 1 then
    for i = lo to min 1 hi do is_prime.(i - lo) <- false done;
  List.iter (fun p ->
    let start = max (p * p) (((lo + p - 1) / p) * p) in
    let j = ref start in
    while !j <= hi do
      is_prime.(!j - lo) <- false;
      j := !j + p
    done
  ) base_primes;
  Array.to_seq is_prime
  |> Seq.filter_mapi (fun i b -> if b then Some (lo + i) else None)
  |> List.of_seq

let () =
  let primes_30 = sieve 30 in
  Printf.printf "Primes up to 30: [%s]\n"
    (String.concat "; " (List.map string_of_int primes_30));
  Printf.printf "π(100) = %d (expected 25)\n" (prime_pi 100);
  Printf.printf "Primes in [10, 50]: [%s]\n"
    (String.concat "; " (List.map string_of_int (segmented_sieve 10 50)))

Key Differences

Aspect	Rust	OCaml
Array init	`vec![true; n+1]`	`Array.make (n+1) true`
Outer loop	`while p * p <= n`	`for p = 2 to isqrt n`
Inner loop	`while m <= n { m += p }`	`let m = ref (p*p); while !m <= n`
Memory (bool)	1 byte/bool (8x waste)	1 word/bool (worse)
Result type	`Vec<bool>` (sieve) or `Vec<usize>`	`bool array` or `int list`
Segmented variant	Manual chunk iteration	Same approach

OCaml Approach

OCaml implements the sieve with Array.make (n+1) true and two nested loops using for and while. The functional equivalent uses Array.iteri for the outer loop, though mutable array mutation is idiomatic here. OCaml's Array.to_seqi |> Seq.filter_map (fun (i, b) -> if b then Some i else None) generates prime sequences lazily. The Bigarray module provides compact bit arrays for memory efficiency. OCaml's Printf.printf easily prints prime counts for verification.

Full Source

#![allow(clippy::all)]
//! # Sieve of Eratosthenes
pub fn sieve(n: usize) -> Vec<bool> {
    let mut is_prime = vec![true; n + 1];
    is_prime[0] = false;
    if n >= 1 {
        is_prime[1] = false;
    }
    for i in 2..=((n as f64).sqrt() as usize) {
        if is_prime[i] {
            for j in (i * i..=n).step_by(i) {
                is_prime[j] = false;
            }
        }
    }
    is_prime
}

pub fn primes_up_to(n: usize) -> Vec<usize> {
    sieve(n)
        .iter()
        .enumerate()
        .filter_map(|(i, &b)| if b { Some(i) } else { None })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_sieve() {
        assert_eq!(primes_up_to(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
    }
}

(* Sieve of Eratosthenes in OCaml *)

(* Return all primes up to and including limit *)
let sieve (limit : int) : int list =
  if limit < 2 then []
  else begin
    let is_prime = Array.make (limit + 1) true in
    is_prime.(0) <- false;
    is_prime.(1) <- false;
    let sqrt_limit = int_of_float (sqrt (float_of_int limit)) in
    for p = 2 to sqrt_limit do
      if is_prime.(p) then begin
        let j = ref (p * p) in
        while !j <= limit do
          is_prime.(!j) <- false;
          j := !j + p
        done
      end
    done;
    (* Collect all primes functionally *)
    Array.to_seq is_prime
    |> Seq.filter_mapi (fun i b -> if b then Some i else None)
    |> List.of_seq
  end

(* Count primes up to n (prime-counting function π(n)) *)
let prime_pi (n : int) : int =
  List.length (sieve n)

(* Segmented sieve for large ranges — sieve [lo, hi] *)
let segmented_sieve (lo : int) (hi : int) : int list =
  let base_primes = sieve (int_of_float (sqrt (float_of_int hi)) + 1) in
  let size = hi - lo + 1 in
  let is_prime = Array.make size true in
  (* 0 and 1 are not prime *)
  if lo <= 1 then
    for i = lo to min 1 hi do is_prime.(i - lo) <- false done;
  List.iter (fun p ->
    let start = max (p * p) (((lo + p - 1) / p) * p) in
    let j = ref start in
    while !j <= hi do
      is_prime.(!j - lo) <- false;
      j := !j + p
    done
  ) base_primes;
  Array.to_seq is_prime
  |> Seq.filter_mapi (fun i b -> if b then Some (lo + i) else None)
  |> List.of_seq

let () =
  let primes_30 = sieve 30 in
  Printf.printf "Primes up to 30: [%s]\n"
    (String.concat "; " (List.map string_of_int primes_30));
  Printf.printf "π(100) = %d (expected 25)\n" (prime_pi 100);
  Printf.printf "Primes in [10, 50]: [%s]\n"
    (String.concat "; " (List.map string_of_int (segmented_sieve 10 50)))

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_sieve() {
        assert_eq!(primes_up_to(20), vec![2, 3, 5, 7, 11, 13, 17, 19]);
    }
}

Deep Comparison

OCaml vs Rust: Sieve Of Eratosthenes

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

Implement a segmented sieve that generates primes in the range [L, R] using only O(sqrt(R)) memory.

Build the smallest prime factor table: spf[i] = smallest prime dividing i, useful for fast factorization.

Compute Euler's totient function for all n ≤ N using a sieve-like approach.

Count twin primes (pairs p, p+2 both prime) up to 10^7 and compare with pi(n) estimates.

Implement a BitVec-backed sieve and measure memory and speed improvement vs Vec<bool>.

Open Source Repos

functional-rust

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

Rust