finding primes very slow in F#
algorithm, f#, primes
Solution
As already mentioned by John, your implementation is slow because it generates some temporary data structures.
In the first case, you are building a list, which needs to be fully created in memory and that introduces significant overhead.
In the second case, you are building a lazy sequence, which does not consume memory (because it is build while it is being iterated), but it still introduces indirection that slows the algorithm down.
In most cases in F#, people tend to prefer readability and so using sequences is a nice way to write the code, but here you probably care more about performance, so I'd avoid sequences. If you want to keep the same structure of your code, you can rewrite `isPrime` like this:
let isPrime n =
let rec nonDivisible by =
if by = 1 then true // Return 'true' if we reached the end
elif n%by = 0 then false // Return 'false' if there is a divisor
else nonDivisible (by - 1) // Otherwise continue looping
n > 1 && nonDivisible (n/2)
This just replaces the sequence and `forall` with a recursive function `nonDivisible` that returns `true` when the number `n` is not divisible by any number between 2 and `n/2`. The function first checks the two termination cases and otherwise performs a recursive call..
With the original implementation, I'm able to find 1000th prime in 1.5sec and with the new one, it takes 22ms. Finding 10000th prime with the new implementation takes 3.2sec on my machine.
Problem
I have answered Project Euler Question 7 very easily using Sieve of Eratosthenes in C and I had no problem with it. I am still quite new to F# so I tried implementing the same technique ``` let prime_at pos = let rec loop f l = match f with | x::xs -> loop xs (l |> List.filter(fun i -> i % x <> 0 || i = x)) | _ -> l List.nth (loop [2..pos] [2..pos*pos]) (pos-1) ``` which works well when pos < 1000, but will crash at 10000 with out of memory exception I then tried changing the algorithm to ``` let isPrime n = n > 1 && seq { for f in [2..n/2] do yield f } |> Seq.forall(fun i -> n % i <> 0) seq {for i in 2..(10000 * 10000) do if isPrime i then yield i} |> Seq.nth 10000 |> Dump ``` which runs successfully but still takes a few minutes. If I understand correctly the first algorithm is tail optimized so why does it crash? And how can I write an algorithm that runs under 1 minute (I have a fast computer)?