使用函数式编程有效地计算素数 [英] Using Functional Programming to compute prime numbers efficiently

问题描述

我通过遍历Euler项目并解决了一些问题来熟悉F#.许多早期的问题由质数组成.环顾四周后，我想到了以下解决方案:

I'm getting acquainted with F# by going over Project Euler and solving some of the problems. Many of the early problems consist of prime numbers. After looking around I came up with the following solution:

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的质数:

This works well, but then I generate all the prime numbers up to 2000000:

let smallPrimes = primesL |> Seq.takeWhile (fun n->n<=2000000)

这需要年龄.很明显，有些事情是在O(N ^ 2)或更坏的情况下完成的.

This takes ages. It's quite obvious something is done in O(N^2) or worst.

我知道我可以编写命令式版本并实现某种筛子，但是我想要坚持使用功能代码.如果我需要当务之急，我会留在C#中.

I know I can write an imperative version and implement a sieve of some sort, but I want to stick to functional code. If I wanted imperative, I would have stayed with C#.

我想念什么?

推荐答案

您可能希望将您的方法与

You may want to compare your approach with my variant of Problem Euler 10 solution

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函数作为共同结果.

It is purely functional, uses sequence cashing, optimized for primality check; also it yields very useful isPrime n function as a co-result.

并应用于原始问题

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

它在不错的2.5秒内完成.这不是很迅速，但足以在少数我的其他Project Euler解决方案中使用此primes序列 (到目前为止，有27、35、37、50、58、69、70、77).

it completes in decent 2.5 s. This is not blasting fast, but was good enough to use this primes sequence in handful of my other Project Euler solutions (27, 35, 37, 50, 58, 69, 70, 77 so far).

关于您的解决方案中缺少的内容-从您的代码中，我相信您在每次对prim的内部调用上都建立了一个全新的序列，即在我的方法使用单个序列来查找已经找到的素数，并且在生成每个下一个素数时仅枚举其缓存的实例.

As to what you're missing in your solution - from your code I believe you're building a brand new sequence on each internal call to prim, i.e. for each natural while my approach uses a single sequence for already found primes and only enumerates its cached instance when producing each next prime.

这篇关于使用函数式编程有效地计算素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！