0

我在 F# 中的质数检查器遇到了一些问题。它似乎没有给出正确的结果，所以我猜我在某个地方搞砸了逻辑，但我不知道在哪里。该实现是一种简单的暴力破解，因此逻辑并不复杂，而且我之前在命令式语言中使用 for 循环实现了类似的解决方案。

let rec isPrime iterator (n : int) = 
                            match iterator with
                            | 1 -> isPrime (iterator + 1) n
                            | a when a = n -> isPrime (iterator + 1) n
                            | _ -> match n % iterator = 0 with
                                    | true -> false
                                    | false -> isPrime (iterator + 1) n
4

1 回答 1

3

正如您在评论中已经发现的那样，问题在于该函数应该终止并说明true迭代器何时到达n. 实际上，您可以通过迭代到 的平方根n或至少n/2因为当您到达n/2时，您知道它将是一个素数，从而使其更快。

这种逻辑似乎更容易使用if而不是match- 尽管您可以通过修复案例来轻松修复它match，但我可能会写如下内容：

let rec isPrime iterator (n : int) = 
  if iterator = n / 2 then true
  elif iterator = 1 then isPrime (iterator + 1) n
  elif n % iterator = 0 then false
  else isPrime (iterator + 1) n

此外，您可能不想将iterator参数公开给用户 - 您可以使用嵌套函数编写代码，该函数调用循环开头iterator = 2（然后您根本不需要这种iterator = 1情况）：

let isPrime (n : int) = 
  let rec loop iterator = 
    if iterator = n/2 then true
    elif n % iterator = 0 then false
    else loop (iterator + 1)
  loop 2
于 2014-11-02T16:50:37.670 回答