Sieve of Eratosthenes (Alice ML)

From LiteratePrograms

Other implementations: Alice ML | Bash | C++ | Forth | Haskell | Java | Python | Python, arrays | Scala

The Sieve of Eratosthenes is an algorithm for rapidly locating all the prime numbers in a certain range of integers. It operates by marking as composite all nontrivial multiples of each prime in sequence until only primes remain unmarked. It is most well-suited to implementation using arrays, which are compact and feature random access.

Alice ML uses an eager evaluation strategy by default but allows expressions and functions to be declared lazy. To begin with, we need a Stream of all integers >= 2. The following function gives us an infinite stream of integers starting from a specified number.

<<sieve.aml>>=
fun lazy integers_starting_from n =
   n :: integers_starting_from(n + 1)

We'll also need a helper function that tells us whether a number is divisable by another number.

<<sieve.aml>>=
fun isDivisible (x, y) = ((x mod y) = 0)

Next we create a function that filters a stream based on a supplied predicate function:

<<sieve.aml>>=
fun lazy stream_filter pred nil = nil
  | stream_filter pred (x::xs) =
      if (pred x)
         then x :: (stream_filter pred xs)
         else stream_filter pred xs;

With these in place, we can construct the Sieve of Eratosthenes

<<sieve.aml>>=
fun lazy sieve stream =
   (hd stream) ::
      (sieve
         (stream_filter
            (fn (x) => not(isDivisible(x, hd stream)))
            (tl stream)))

To construct the infinite stream of primes, we supply the sieve with the list of integers starting at 2.

<<sieve.aml>>=
val primes = sieve(integers_starting_from 2);

To get a calculation on the nth prime, we force a calculation on the primes stream:

<<sieve.aml>>=
val thousandth_prime = List.nth(primes, 1000-1)

Download code