Finding primes is very slow in F #

Question

I answered Project Euler Question 7 very easily using Sieve of Eratosthenes in C and I had no problems with it.

I'm still new to F #, so I tried to implement 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 fail at 10000 with memory exception

Then I tried to change 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 is successful, 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 works less than 1 minute (I have a fast computer)?

Answer 1

, , .

• , , .

• , ( ), , .

F # , - , , , , . , isPrime :

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)

forall nonDivisible, true, n 2 n/2. .

1000- 1.5 , 22 . 10000- 3,2 .

Answer 2

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)

. , , . , , , . pos=10 000 , 10 000 * 10 000 * 4 = 400MB 800MB ( F # - ). , , , , GC. . , OutOfMemoryException.

,

let isPrime n = 
    n > 1 && 
    seq { for f in [2..n/2] do yield f } 
    |> Seq.forall(fun i -> n % i <> 0)

, .

F # fooobar.com/questions/38313/..., , .