我正在学习 haskell,方法是学习 learnyouahaskell,完成 haskellwiki 的 99 个问题,以及投影欧拉问题。我昨天大部分时间都在研究 PE problem 3 ,没有成功,因为我的所有解决方案都会运行很长时间并使我的计算机陷入困境。我通读了 haskell wiki page on prime numbers但仍然没有成功,所以我放弃并查看了发布的解决方案 here .
代码如下:
primes = 2 : filter ((==1) . length . primeFactors) [3,5..]
primeFactors n = factor n primes
where
factor n (p:ps)
| p*p > n = [n]
| n `mod` p == 0 = p : factor (n `div` p) (p:ps)
| otherwise = factor n ps
速度很快,它会立即吐出答案,但我无法全神贯注于这段代码。特别是 primes
函数和过滤器发生了什么,以及它如何与调用 primeFactors
和 primeFactors
的 primes
一起工作调用 primes
。如果我在 GHCI 中运行 primes
,它会创建一个无限的素数列表,我不知道为什么。
最佳答案
我目前正在研究 Euler 项目自己提出的问题,并实现了一个基于素筛的非常基本的解决方案,并且遇到了与您的解决方案相同的问题,因为它会在任意数量的中等大小或更大的情况下运行很长时间
正如 meditans 在他对你的问题的评论中所说,看看 this question ,尤其是 Will Ness 的第一条评论和接受的答案,这两个都对我帮助很大。
我还发现这两个 HaskellWiki 页面当时帮助我理解了解决方案以及为其他问题编写了我自己的函数。
关于algorithm - 使用 Haskell 计算质因数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25452021/