Haskell素数测试

Question

我是 Haskell 的新手，我正在尝试一下：

isPrime :: Integer->Bool
isPrime x = ([] == [y | y<-[2..floor (sqrt x)], mod x y == 0])

我有几个问题。

1. 为什么当我尝试加载 .hs 时，WinHugs 说：定义 isPrime 需要 (Floating Integer, RealFrac Integer) 实例？
2. 当解释器在正确的集合中找到一个元素时，它会立即停止还是计算所有集合？我想你知道我的意思。

对不起我的英语。

Answer 1

1) 问题是 sqrt 的类型为 (Floating a) =>;一个-> a，但您尝试使用整数作为参数。因此，您必须首先将整数转换为浮点数，例如通过编写 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 的元素：

filter (\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..]))

如果这对你来说看起来很 lispy，请替换一些括号带有 $

isPrime x = null $ 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

您可以通过将 null $ 过滤器替换为 not $ any 来使其几乎“人类可读”：

isPrime x = not $ any divisible $ takeWhile notTooBig [2..] where
     divisible y = x `mod`y == 0
     notTooBig y = y*y <= x

Answer 2

1. 因为 sqrt 的类型为 Floating a =>;一个->一个。这意味着输入必须是Floating类型，并且输出也将是相同的类型。换句话说，x 需要是 Floating 类型。但是，您将 x 声明为 Integer 类型，它不是 Floating 类型。此外，floor 需要 RealFrac 类型，因此 x 也需要是该类型。

   错误消息建议您通过将 Integer 设为 Floating 类型（通过定义一个实例 Floating Integer）来解决该问题（对于RealFrac）。

   当然，在这种情况下这不是正确的方法。相反，您应该使用 fromIntegral 将 x 转换为 Real （这是 Floating 和 的实例） RealFrac），然后将其赋予 sqrt。

2. 是。 == 看到右操作数至少有一个元素，它知道它不等于 []，因此返回 False。

   话虽如此，null 是一种比 [] == 更惯用的检查列表是否为空的方法。

Answer 3

关于第二点，就停止了，例如：

[] == [x | x <- [1..]]

Returns False

Answer 4

Landei 的解决方案很棒，但是，如果您想要更高效的 1 实现，我们有（感谢 BMeph）：

-- list of all primes
primes :: [Integer]
primes = sieve (2 : 3 : possible [1..]) where
     sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0]
     possible (x:xs) = 6*x-1 : 6*x+1 : possible xs

isPrime :: Integer -> Bool
isPrime n = shortCircuit || (not $ any divisible $ takeWhile inRangeOf primes) where
    shortCircuit = elem n [2,3] || (n < 25 && ((n-1) `mod` 6 == 0 || (n+1) `mod` 6 == 0))
    divisible y = n `mod` y == 0
    inRangeOf y = y * y <= n

“效率”来自于常数素数的使用。它以两种方式改进了搜索：

1. Haskell 运行时可以缓存结果，因此后续调用不会被评估
2. 它通过逻辑消除了一系列数字
   请注意，sieve 值只是一个递归表，其中表示
   该列表是素数，并将其添加到其中。对于其余列表，如果没有
   组成数字的列表中已有的其他值，那么它也是素数
   possible 是所有可能的素数的列表，因为所有可能的素数都在
   形成 6*k-1 或 6*k-1（2 和 3 除外）
   同样的规则也适用于 shortCircuit，以快速摆脱计算

脚注（DF
）
1 这仍然是一种寻找素数的极其低效的方法。如果您需要大于几千的素数，请不要使用试除法，而应使用筛子。还有几个更多 在 hackage 上实现高效。

Answer 5

1. 我认为 WinHugs 需要导入 Integer 等模块... Try Int
2. 解释器不会计算任何内容，直到您调用例如 isPrime 32 然后它将延迟计算表达式。

PS 你的 isPrime 实现不是最好的实现！