通过回顾 Project Euler 并解决一些问题,我逐渐熟悉了 F#。许多早期问题都由素数组成。环顾四周后,我想出了以下解决方案:
let primesL =
let rec prim n sofar =
seq { if (sofar |> List.forall (fun i->n%i <>0L)) then
yield n
yield! prim (n+1L) (n::sofar)
else
yield! prim (n+1L) sofar }
prim 2L []
这很有效,但随后我生成了 2000000 以内的所有素数:
let smallPrimes = primesL |> Seq.takeWhile (fun n->n<=2000000)
这需要ages。很明显,某些事情是在 O(N^2) 或者最坏的时间内完成的。
我知道我可以编写一个命令式版本并实现sieve http://en.wikipedia.org/wiki/Generating_primes某种程度,但我想坚持使用功能代码。如果我想要命令式,我会继续使用 C#。
我缺少什么?
我不会在这里写一个很长的答案,而是建议您参考梅丽莎·奥尼尔关于埃拉托色尼筛子的伟大论文 http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)