埃拉托色尼 SML 筛法

Question

我是 SML 新手。我正在尝试创建一个函数，该函数使用 Eratosthenes 筛法输出小于或等于给定整数 n > 2 的所有素数的列表。我运行遇到了一个问题，但是输出仅显示为 [1]。我希望能够输入 5 并得到 [1,3,5] 作为结果。

到目前为止，这是我的代码，我很新，所以我知道它很可能写得不正确。

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), []);

Answer 1

您的 removeMult 功能运行良好。

您的 sieve 函数也能完美运行。太完美了。

考虑一下调用 dosieve(10) 时会发生什么：

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

从那里开始：

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

糟糕。您删除了 1 的所有倍数，但当然它们是 1.

的所有倍数

可能是这样的：

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

埃拉托色尼 SML 筛法

SML Sieve of Eratosthenes

primes

function

sml

smlnj

sieve-of-eratosthenes