Primefactors in F#

Question

I am trying to learn F#.
I wrote a function that factors out primes.

let PrimeFactors x =
  let rec PrimeFactorsRecursive x div list =
     if x % div = 0 then PrimeFactorsRecursive (x/div) div list @ [div]
     elif div > int(System.Math.Sqrt(float(x))) then 
       if x > 1 then list @ [x]
       else list
     else PrimeFactorsRecursive x (div + 1) list
  PrimeFactorsRecursive x 2 []

Now I am unsure if this is a good F# function or if it is more like "c#, written in f#".

Is there a "more" functional way to write this code?

Answer 1

You could probably use guarded patterns to reduce the if-expression nesting. Other than that it looks like perfectly reasonable idiomatic functional code to me.

Answer 2

The primal problem in your code is that you use @ to concat two lists. Concating two lists costs linear time, not constant time.

The constant way is to add the new prime number to the head of a list using :: operator as shown below:

let primeFactors x = 
    let rec fact x div list = 
        if x % div = 0 then
            fact (x/div) div (div::list)
        elif div > int(sqrt (float x)) then
            if x > 1 then x::list
            else list
        else
            fact x (div+1) list
    fact x 2 []

Also let bind values are usually following camleStyle naming conversions.

Answer 3

Another "improvement" not yet mentioned is to use piping so that instead of

int(System.Math.Sqrt(float(x)))

you have

(x |> float |> sqrt |> int)