Skip to content

Instantly share code, notes, and snippets.

Created November 21, 2022 11:59
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
What would you like to do?
Generate prime numbers using an online Sieve of Eratosthenes
let primes =
let a = {2} in
let grow() =
let p0 = Array.get a (Array.length a - 1) + 1 in
let b = Array.init p0 [_ → True] in
let () =
Array.fold [(), di →
let rec loop i =
if i >= Array.length b then () else
let () = Array.Unsafe.set b i False in
loop(i+di) in
let i0 = floor(p0 / di) * di in
loop(if i0<p0 then i0+di-p0 else i0-p0) ] () a in
let f ((a, i), b) =
(if b then Array.Unsafe.append a (p0+i) else a), i+1 in
let _ = Array.fold f (a, 0) b in
() in
let rec loop n =
if n < Array.length a then Array.get a n else
let () = grow() in
loop n in
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment