REVISED: Sunday, September 14, 2025
1. OCAML SIEVE OF ERATOSTHENES
(* SieveOfEratosthenes.ml *)
(* Function to generate a list of integers from 2 up to a given number 'n'. *)
(* 'let rec' defines a recursive function named 'range'. *)
(* It takes two arguments: 'start' and 'stop'. *)
let rec range start stop =
(* The 'if' condition checks if the 'start' value has exceeded the 'stop' value. *)
if start > stop then
[] (* If true, it returns an empty list, terminating the recursion. *)
else
(* If false, it prepends the current 'start' value to the list *)
(* generated by a recursive call to 'range' with 'start + 1'. *)
(* '::' is the "cons" operator for adding an element to the head of a list. *)
start :: range (start + 1) stop
(* The core Sieve of Eratosthenes algorithm implemented as a recursive function. *)
(* 'let rec' defines a recursive function named 'sieve'. *)
(* It takes one argument: a list of integers 'nums'. *)
let rec sieve nums =
(* 'match' is used for pattern matching on the input list 'nums'. *)
match nums with
| [] -> [] (* Case 1: If the list is empty, return an empty list. *)
| p :: rest -> (* Case 2: If the list is not empty, it's deconstructed. *)
(* 'p' is the head of the list (the first element, which is a prime). *)
(* 'rest' is the tail of the list (all other elements). *)
(* The prime 'p' is prepended to the result of the recursive call. *)
p :: sieve (List.filter (fun n -> n mod p <> 0) rest)
(* 'List.filter' creates a new list containing only the elements from 'rest' *)
(* for which the anonymous function '(fun n -> n mod p <> 0)' returns true. *)
(* This function keeps numbers 'n' that are NOT divisible by 'p'. *)
(* The result of this filter (the new, smaller list) is passed to the next recursive 'sieve' call. *)
(* Main execution block *)
let () =
(* We need to estimate an upper bound to find 100 primes. *)
(* The nth prime is approximately n * log(n). For n=100, this is ~100 * log(100) ≈ 460. *)
(* We'll use a slightly larger, safer upper bound, like 600, to ensure we find enough primes. *)
let upper_bound = 600 in
(* Generate the initial list of integers from 2 to the upper_bound. *)
let initial_numbers = range 2 upper_bound in
(* Apply the sieve algorithm to the list to get all primes up to the bound. *)
let all_primes = sieve initial_numbers in
(* We only want the first 100 primes. 'List.to_seq' converts the list to a sequence, *)
(* 'Seq.take 100' gets the first 100 elements, and 'List.of_seq' converts it back to a list. *)
let first_100_primes = List.of_seq (Seq.take 100 (List.to_seq all_primes)) in
(* 'List.iter' applies a function to each element of the list. *)
(* Here, it prints each prime number followed by a space. *)
List.iter (fun p -> print_int p; print_string " ") first_100_primes;
(* 'print_newline ()' prints a newline character for clean formatting at the end. *)
print_newline ()
2. CONCLUSION
OCaml version: The OCaml toplevel, version 5.3.0
Coq-LSP version: 0.2.3
PS C:\AI2025> & C:/Users/User/OneDrive/Documents/DOCUMENTS/AI2025/.venv/Scripts/Activate.ps1
(.venv) PS C:\AI2025> ocaml C:\AI2025\SieveOfEratosthenes.ml
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
(.venv) PS C:\AI2025>
3. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Pierce, Benjamin C., et al., editors. Logical Foundations. Vol. 1 of Software Foundations. Electronic Textbook, 2024. Version 6.7, http://softwarefoundations.cis.upenn.edu.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
