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'任何'函数 - 素性检查

回答

相关问题