SML Sieve of Eratosthenes

user_17936734 0
Viewed 107

I am new to SML. I am trying to create a function that outputs a list of all prime numbers which are smaller than or equal to a given integer n > 2 using the Sieve of Eratosthenes. I am running into a problem however where the output is only showing as [1]. I would like to be able to have an input such as 5 and get [1,3,5] as a result.

This is my code so far, I am very new so I know it is most likely not written correctly.

fun createList(ending) =
  let 
    fun createListX(start, ending) =
      if start = ending then []
      else start :: createListX(start + 1, ending)
  in
    createListX(1, ending + 1)
  end;

fun removeMult ([], n) = []
  | removeMult (x::xs, n) = 
      if x mod n = 0 then 
        removeMult(xs, n)
      else 
        x :: removeMult(xs, n);

fun sieve([], primes) = primes
  | sieve(n::ns, primes) = sieve(removeMult(ns, n), n :: primes);

fun dosieve(n) = sieve(createList(n-1), []);
smlnj sieve-of-eratosthenes primes sml function
1 Answers

Your removeMult function works nicely.

Your sieve function works perfectly too. Too perfectly.

Consider what happens when you call dosieve(10) for instance:

dosieve(10)
sieve(createList(9), [])
sieve([1,2,3,4,5,6,7,8,9], [])

From there:

sieve(removeMult([2, 3, 4, 5, 6, 7, 8, 9], 1), 1 :: [])
sieve([], [1])
[1]

Oops. You removed all multiples of 1, but of course they're all multiples of 1.

Perhaps something like:

fun sieve([], primes) = primes
  | sieve(1::ns, primes) = sieve(ns, 1 :: primes)
  | sieve(n::ns, primes) = sieve(removeMult(ns, n), n :: primes);
user_152613150
Related