相关疑难解决方法(0)

我通过浏览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)

这需要很长时间.很明显,事情是在O(N ^ 2)或最差的情况下完成的.

我知道我可以写一个命令式版本并实现某种类型的筛子,但我想坚持使用功能代码.如果我想要命令,我会留在C#.

我错过了什么？