哈斯克尔素数测试

本文介绍了哈斯克尔素数测试的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 我是Haskell的新手，并且尝试了一下： isPrime :: Integer-> Bool isPrime x =（[] == [y | y 我有几个问题。名为.hs，WinHugs说：的实例（浮动整数，RealFrac整数）为 isPrime 当解释器在右边的集合中找到一个元素时，立即停止或计算所有集合？我想你明白我的意思。 >解决方案 1）问题是 sqrt 的类型为（Floating a）=> a - >一个，但您尝试使用整数作为参数。所以你必须先将Integer转换为Floating，例如通过写 sqrt（fromIntegral x） 2）我没有理由认为==不应该是懒惰的，但是为了测试一个空集合，你可以使用 null 函数（这肯定是懒惰的，因为它在无限列表上工作）： isPrime :: Integer-> Bool isPrime x = null [y | y 但为了获得一个更习惯的解决方案，将问题分解为更小的子问题。首先，我们需要一个包含y * y takeWhile（\y - > ; y * y 然后我们只需要元素除以x： 过滤器（\y - > x`mod`y == 0）（takeWhile（\y - > y * y< = x）[2 ..]） 检查这个列表是否为空： isPrime x = null（filter（\y - > x`mod`y = = 0）（takeWhile（\y-> y * y< = x）[2 ..]）） 如果这看起来赞同你，用$ isPrime x = null替换一些parens $ filter（\y-> x`mod` y == 0）$ takeWhile（\y-> y * y< = x）[2 ..] 为了更加清晰，您可以将lambda外包： isPrime x = null $ filter divisible $ takeWhile notTooBig [2 ..] where divisible y = x`mod`y == 0 notTooBig y = y * y 您可以通过替换$ $ b isPrime x = not $任意可分割$ takeWhile notTooBig [2 ..]其中 divisible y = x`mod`y == 0 notTooBig y = y * y I'm new to Haskell, and I'm trying a bit:isPrime :: Integer->BoolisPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])I have a few questions.Why when I try to load the .hs, WinHugs say: Instances of (Floating Integer, RealFrac Integer) required for definition of isPrime?When the interpreter finds one element in the right set, it immediately stops or it computes all the set? I think you know what I mean.Sorry about my english. 解决方案 1) The problem is that sqrt has the type (Floating a) => a -> a, but you try to use an Integer as argument. So you have to convert your Integer first to a Floating, e.g. by writing sqrt (fromIntegral x)2) I see no reason why == shouldn't be lazy, but for testing for an empty collection you can use the null function (which is definitely lazy, as it works on infinite lists):isPrime :: Integer->BoolisPrime x = null [y | y<-[2..floor (sqrt (fromIntegral x))], x `mod` y == 0]But in order to get an more idiomatic solution, break the problem into smaller sub-problems. First, we need a list of all elements y with y*y <= x:takeWhile (\y -> y*y <= x) [2..]Then we need only the elements that divide x:filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..])Then we need to check if that list is empty:isPrime x = null (filter (\y -> x `mod`y == 0) (takeWhile (\y -> y*y <= x) [2..]))And if this looks to lispy to you, replace some of the parens with $isPrime x = null $ filter (\y -> x `mod` y == 0) $ takeWhile (\y -> y*y <= x) [2..]For additional clarity you can "outsource" the lambdas:isPrime x = null $ filter divisible $ takeWhile notTooBig [2..] where divisible y = x `mod`y == 0 notTooBig y = y*y <= xYou can make it almost "human readable" by replacing null $ filter with not $ any:isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where divisible y = x `mod`y == 0 notTooBig y = y*y <= x 这篇关于哈斯克尔素数测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！