利用函数式编程高效计算素数

Question

通过查看Project并解决一些问题，我熟悉了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)

这需要很长时间。很明显，在O(N^2)或最坏的情况下做了一些事情。

我知道我可以编写一个命令式版本并实现某种类型的筛，筛，但是我想坚持函数式代码。如果我希望命令式，我会留在C#。

我遗漏了什么？

Answer 1

您可能希望将您的方法与问题Euler 10解的我的变体进行比较。

let rec primes = 
    Seq.cache <| seq { yield 2; yield! Seq.unfold nextPrime 3 }
and nextPrime n =
    if isPrime n then Some(n, n + 2) else nextPrime(n + 2)
and isPrime n =
    if n >= 2 then
        primes 
        |> Seq.tryFind (fun x -> n % x = 0 || x * x > n)
        |> fun x -> x.Value * x.Value > n
    else false

它是纯功能的，使用序列兑现，为质性检查进行优化；同时，它还产生了非常有用的isPrime n函数作为共同结果。

并将其应用于原问题

let problem010 () =
    primes
    |> Seq.takeWhile ((>) 2000000)
    |> (Seq.map int64 >> Seq.sum)

它在体面的2.5 s中完成。这还不够快，但足够好地使用这个primes序列在少数我的其他项目Euler解决方案 (27，35，37，50，58，69，70，77到目前为止)。

至于解决方案中缺少的内容--从您的代码中，我相信您正在为每个对prim的内部调用构建一个全新的序列，即对于每个自然调用，而我的方法使用一个单个序列来表示已经找到的素数，并且只有在生成每个下一个素数时枚举它的缓存实例。

Answer 2

与其在这里写一个长篇的答案，我建议您参考梅丽莎·奥尼尔关于埃拉托斯提尼筛的伟大论文。

Answer 3

首先，它是O(n^2) --记住在每次迭代中都使用List.forall。

其次，如果经常使用生成器，则应该缓存结果(因此每个素数只计算一次)：

let primesL =
    let rec prim n sofar = 
        seq { if (sofar |> List.forall (fun i -> n % i <> 0UL)) then
                  yield n
                  yield! prim (n + 1UL) (n::sofar)
              else
                  yield! prim (n + 1UL) sofar }
    prim 2UL []
    |> Seq.cache