Haskell'任何'函數 - 素性檢查

我試圖在Haskell中定義一個is_prime函數。任何人都可以使用任何函數指出問題嗎？此外，我知道下面的代碼是天真的，但我正在學習語言，所以從babysteps開始。Haskell'任何'函數 - 素性檢查

is_prime 0 = False 
is_prime 1 = False 
is_prime 2 = True 
is_prime n = any [n `mod` k == 0 | k <- [2.. sqrt n]]

來源

2011-12-17 S0rin

請注意，除了@ Jan對使用any的解決方法之外，順便說一句，你似乎期待從'any'得到的函數被稱爲'或' - 並且使用'sqrt' ，你的檢查是錯誤的，你錯過了一個'not'，因爲它會返回'True'爲合成數字，'False'爲質數（2除外）。 – 2011-12-17 22:59:46

您也可以將解決方案想象爲製作所有除數列表並檢查列表是否爲空（或不）：'null [k | k < - [2..sqrt n]，n \'mod \'k == 0]' – 2011-12-17 23:19:30

好問題。在這種情況下，查看錯誤並不難，但將來您可能應該包含一條錯誤消息，以便更容易地查看問題所在。 – Boris 2013-09-11 07:55:45

的any類型是(a -> Bool) -> [a] -> Bool，所以它接受一個謂語和集合。所以，你應該重寫你的最後情況下，例如

is_prime n = not $ any (\k -> n `mod` k /= 0) 
         [2 .. ceiling $ sqrt $ fromIntegral n]

fromIntegral是必要的，因爲sqrt的類型是Floating a => a -> a，而你的n是一個整數。隨後，如果沒有ceiling，any的第二個參數將爲Floating t => [t]。這將打破，因爲調用mod，其類型爲Integral a => a -> a -> a，對非整數類型是非法的。

如果你想尋找一些其他的實現，我可以推薦例如this discussion。

來源

2011-12-17 22:51:10 Jan

接受的答案是，在我看來，不正確的is_prime函數實際上返回False如果n是一個素數，這裏的原因。

any function data返回True只要它遇到在data這樣的元件，其function data是True。
\k -> mod n k /= 0返回True如果適用於不的數字除以n。
因此，any回報True如果在給定列表中一個數字，不鴻溝，我們要檢查素性數量n和False如果有是之一。
因此，對於任何數量的is_prime回報True即是任意數量的列表[2 .. ceiling $ sqrt $ fromIntegral n]，例如，4這顯然不是的黃金分割。

隨着中說，正確的解決方案應該是這樣的：

is_prime n = not $ any (\k -> n `mod` k == 0) [2 .. ceiling $ sqrt $ fromIntegral n]

這是因爲許多n是素數，如果它不和sqrt n之間的任意數字的倍數。

來源

2016-12-01 19:06:33 ForceBru

Haskell'任何'函數 - 素性檢查

回答

相關問題