0

在过去的几天里，我一直在通过 Learn You A Haskell 学习 Haskell。我一直在尝试完成一些 Project Euler 问题，其中一些需要素数。但是，我编写的尝试生成一些函数（在本例中为低于 20000 的素数）的函数输出不正确。当我运行它时，GHCi返回'[1, '并且似乎不会终止。我正在使用的代码是：

sieve :: (Integral a) => a -> [a] -> [a]
sieve 20000 list = list
sieve n (x:xs) = sieve (n+1) $ x:(filter (\q -> q `mod` n /= 0) xs)

primesto20000 = sieve 2 [1..20000]

然后我打电话primesto20000。我知道该功能可能效率低下，我主要是就我必须犯的语法/过程错误寻求帮助。
谢谢

4

2 回答 2

2

您正在过滤掉每个数字的倍数，而不仅仅是素数。你想检查除以x，而不是n。（事实上​​，我不确定你是否需要n在sieve函数中；只需让你的primesto20000函数生成适当的输入列表，然后传递它。）

于 2013-02-05T09:08:41.357 回答
2

您的代码中有两个问题：

  • 因为它的时间复杂度（我猜是二次方），它没有在合理的时间内完成，而且它似乎只是挂起。如果将 20000 替换为 200，它将完成，但结果将是[1].
  • 另一个问题是，对于每个n你想要过滤的所有数字都可以n被大于. n没有这个条件，你过滤n自己，结果就是过滤掉所有的数字。

更正后的版本可能如下所示（具有参数化限制）：

limit :: Integral a => a
limit = 20000

sieve :: (Integral a) => a -> [a] -> [a]
sieve n list | n == limit
    = list
sieve n (x:xs)
    = sieve (n+1) $ x : (filter filt xs)
  where
    -- filter everything divisible by `n`, but not `n` itself.
    filt q = (q <= n) || (q `mod` n /= 0)

primesto20000 = sieve 2 [1..limit]
于 2013-02-05T09:13:48.520 回答