Finding Prime Factors in F#

After having seen a few presentations on F# over the last few months, I’ve been looking for some really simple problems to get me started, and this code golf question inspired me to see if I could factorize a number in F#. I started off by doing it in C#, taking the same approach as the answers on the code golf site (which are optimised for code brevity, not performance):

var n = 502978;
for (var i = 2; i <= n; i++)
{
    while (n%i < 1)
    {
        Console.WriteLine(i);
        n /= i;
    }
}

Obviously it would be possible to try to simply port this directly to F#, but it felt wrong to do so, because there are two mutable variables in this approach (i and n). I started wondering if there was a more functional way to do this working entirely with immutable types.

The algorithm we have starts by testing if 2 is a factor of n. If it is, it divides n by 2 and tries again. Once we’ve divided out all the factors of 2, we increment the test number and repeat the process. Eventually we get down to to the final factor when i equals n.

So the F# approach I came up with, uses a recursive function. We pass in the number to be factorised, the potential factor to test (so we start with 2), and an (immutable) list of factors found so far, which starts off as an empty list. Whenever we find a factor, we create a new immutable list with the old factors as a tail, and call ourselves again. This means n doesn’t have to be mutable – we simply pass in n divided by the factor we just found. Here’s the F# code:

let rec f n x a = 
    if x = n then
        x::a
    elif n % x = 0 then 
        f (n/x) x (x::a)
    else
        f n (x+1) a
let factorise n = f n 2 []
let factors = factorise 502978

The main challenge to get this working was figuring out where I needed to put brackets (and remembering not to use commas between arguments). You’ll also notice I created a factorise function, saving me passing in the initial values of 2 and an empty list. This is one of F#’s real strengths, making it easy to combine functions like this.

Obviously there are performance improvements that could be made to this, and I would also like at some point to work out how to make a non-recursive version of this that still uses immutable values. But at least I now have my first working F# “program”, so I’m a little better prepared for the forthcoming F# Tutorial night with Phil Trelford at devsouthcoast.

If you’re an F# guru, feel free to tell me in the comments how I ought to have solved this.