Using functional programming to efficiently calculate prime numbers

Question

I get to know F # by going through Project Euler and solving some problems. Many of the early problems consist of prime numbers. 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 [] 

This works well, but then I generate all primes up to 2,000,000:

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

It takes a lot of time. Obviously, something is being done in O (N ^ 2) or worse.

I know that I can write an imperative version and implement a sieve , but I want to stick to the functional code. If I wanted to insist, I would stay with C #.

What am I missing?

Answer 1

You can compare your approach with my solution to the Euler 10 problem

 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 

It is purely functional, uses a cashing sequence optimized for authentication; it also gives a very useful function isPrime n as a joint result.

And applies to the original problem

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

it ends in a decent 2.5 s . It doesn't work fast, but is good enough to use this sequence of primes in several of my other Project Euler solutions (27, 35, 37, 50, 58, 69, 70, 77).

What is missing in your decision - from your code, I believe that you create a completely new sequence for each prim internal call, that is, for every natural call, while my approach uses single for primes already found and only lists its cached instance when creating each next prime number.

Answer 2

Instead of writing a long answer here, I refer you to Melissa O'Neill's long article on the sieve of Eratosthenes .

Answer 3

The first is O(n^2) - remember that you use List.forall in every iteration.

Secondly, if you use the generator a lot, you should cache the results (so that every prime number is calculated only once):

 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 

Answer 4

What do you really want here - is it a sieve? I wrote a pretty fast F # sieve before this:

Problem with F # parallelization when calculating ideal numbers?

Answer 5

Use the Miller-Rabin Primitive Test for more than a large large number