哈斯克尔素数测试 [英] Haskell prime test

问题描述

我是Haskell的新手，并且尝试了一下：

  isPrime :: Integer-> Bool 
 isPrime x =（[] == [y | y < -  [2..floor（sqrt x）]，mod xy == 0]）
   
 
 
我有几个问题。名为.hs，WinHugs说：的实例（浮动整数，RealFrac整数）为 isPrime   
 
当解释器在右边的集合中找到一个元素时，立即停止或计算所有集合？我想你明白我的意思。     
     >解决方案

1）问题是 sqrt 的类型为（Floating a）=> a - >一个，但您尝试使用整数作为参数。所以你必须先将Integer转换为Floating，例如通过写 sqrt（fromIntegral x）

2）我没有理由认为==不应该是懒惰的，但是为了测试一个空集合，你可以使用 null 函数（这肯定是懒惰的，因为它在无限列表上工作）：

  isPrime :: Integer-> Bool 
 isPrime x = null [y | y < -  [2..floor（sqrt（fromIntegral x））]，x`mod` y == 0] 
  

但为了获得一个更习惯的解决方案，将问题分解为更小的子问题。首先，我们需要一个包含y * y <= x的所有元素y的列表：

  takeWhile（\y  - > ; y * y <= x）[2 ..] 
  

然后我们只需要元素除以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 <= x 
  
您可以通过替换$ 
 $ b 
  isPrime x = not $任意可分割$ takeWhile notTooBig [2 ..]其中
 divisible y = x`mod`y == 0 
 notTooBig y = y * y <= x 
  
 
I'm new to Haskell, and I'm trying a bit:
isPrime :: Integer->Bool
isPrime 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->Bool
isPrime 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 <= x
You 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


                        
这篇关于哈斯克尔素数测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！