素数检查

Question

我在使用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 

Answer 1

正如你已经在评论想通了，问题是，功能应该终止，并说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