使用函数编程有效地计算素数

Question

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

我错过了什么？

Answer 1

我不是在这里写一个很长的答案,而是提到Melissa O'Neill关于Eratosthenes筛子的伟大论文.

Answer 2

您可能希望将您的方法与我的Problem 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秒.这不是快速爆破,但足以primes在我的其他Project Euler解决方案中使用这个序列(到目前为止分别为27,35,37,50,58,69,70,77).

至于你在解决方案中缺少什么 - 从你的代码中我相信你在每个内部调用上构建一个全新的序列prim,即每个自然序列,而我的方法对已经找到的素数使用单个序列并且只枚举其缓存生成每个下一个素数时的实例.