素數檢查

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