Haskell寻找素数的列表理解

我试图使用列表解析尽可能简洁地找到所有素数小于某个整数n。我正在学习Haskell，这只是一个练习。我想写这样的：Haskell寻找素数的列表理解

isqrt :: Integral a => a -> a 
isqrt = floor . sqrt . fromIntegral 

primes :: Integral a => a -> [a] 
primes n = [i | i <- [1,3..n], mod i k /= 0 | k <- primes (isqrt i)]

哪个当然不起作用。有一种方法可以在列表理解中获得列表理解吗？

这是我得到的错误：

exercise-99-1.hs:138:39: Not in scope: `k' 

exercise-99-1.hs:138:46: 
    Illegal parallel list comprehension: use -XParallelListComp 

exercise-99-1.hs:138:68: Not in scope: `i'

但是 - 我是不是真的期待语法甚至是合法的:-)

这样做的目的是为了尽可能直接翻译：“primes n =该组奇数的i小于n使得i不是整除任何k，对于集合中的所有k：primes (isqrt i)” - 更多或更少。（我希望我明白了吗？）

谢谢！

来源

2011-05-22 Frank

不起作用是非常无益的。发布错误。 – 2011-05-22 00:47:16

你可以把这个错误放入你的文章的正文吗？谢谢。 – 2011-05-22 00:59:56

这是一个：['[n | n < - [2..545]，[] < - [[j | i < - [2..n-2]，j < - [i * i，i * i + i..n]，j == n]]]']（http://stackoverflow.com/questions/ 37103662/programming-haskell-code-list-of-primes/37148656＃37148656） - 审判分裂和Eratosthenes筛的种类。 – 2016-07-31 00:10:30

我做了以下一些进展：

primes :: Integral a => a -> [a] 
primes 2 = [2] 
primes n = 2:[i | i <- [3,5..n], all (\k -> if (mod i k /= 0) then True else False) 
            (primes (isqrt i))]

是否有写的拉姆达谓语较短的方法吗？

编辑：是的，感谢评论中的评论！

primes :: Integral a => a -> [a] 
primes 2 = [2] 
primes n = 2:[i | i <- [3,5..n], all ((/= 0) . mod i) (primes (isqrt i))]

来源

2011-05-22 01:47:50 Frank

有趣的是，它甚至可以与“素数2”线一起工作... – Frank 2011-05-22 02:36:38

永远不要说'如果...那么真的其他假'。相反，只要说'''部分：'\ k - > mod ik/= 0' – Phob 2011-05-22 02:36:46

如果这是你的事情，你也可以使它成为免费的： '（（/ = 0）.mod i）' – Phob 2011-05-22 02:37:25

你的代码，

primes n = [i | i <- [1,3..n], mod i k /= 0 
       | k <- primes (isqrt i)]

被解释为平行列表理解;即代替两台发电机通常嵌套时尚相结合，它们被组合在并行：

primes n = [i | (i,k) <- zip [i | i <- [1,3..n], mod i k /= 0] 
            -- not in scope: k^
          [k | k <- primes (isqrt i)] ] 
            -- not in scope: i^

相反，表达您的本意，它可以写成

primes 1 = [] 
primes n = 2:[i | i <- [3,5..n], and [mod i k /= 0 | k <- primes (isqrt i)]]

因此具有列表理解中的列表理解 - 但作为警卫的一部分，而不是生成器。功能and :: [Bool] -> Bool使这成为可能。

顺便说一句，呼吁primes递归每个新的候选i使得它运行缓慢，运行时间增长过快，empirically：

> length $ primes 10000  -- => 1229 (0.50 secs) 

> length $ primes 20000  -- => 2262 (1.40 secs) 

> logBase (2262/1229) (1.4/0.5)  -- => 1.6878  ~ n^1.69 

> length $ primes 40000  -- => 4203 (4.07 secs) 

> logBase (4203/2262) (4.07/1.4)  -- => 1.7225  ~ n^1.72

优化审判庭通常在运行〜n的^1.4..1.45，Eratosthenes的基于列表的筛子〜n ^1.2..1。25和，如果在可变阵列最佳实施，在〜n的^1.0..1.1（与Ñ素数的产生数，不的上限）。

来源

2016-08-01 06:44:17

Haskell寻找素数的列表理解

回答

相关问题