Getting Prime Factors in F# (with Good Math)

I've been working through Project Euler to get better at F#. There's a lot of math involved in some of these, and being able to calculate prime factors becomes important. I found this out when working on Euler Problem #3 and working on Euler Problem #5 (which I'll be writing about soon).

For Euler Problem #3, I did not do true prime factoring of the numbers. Instead, I was finding the factors of the numbers that were primes (there's a subtle difference). One problem with my previous solution for finding primes is that my math was bad.

The solution I came up with worked for the sample number and the target number specified in the problem, but it would return incomplete results with certain other values. So, I needed to look for a true prime factoring process.

[Update: Collected articles for the first 10 Euler Problems in F# are available here: Jeremy Explores Functional Programming.]

Calculating Prime Factors Manually
Calculating prime factors is something that I learned many years ago (probably in 6th grade). The prime factors of a number is the set of prime numbers which when multiplied together give us the original number.

Here's an example: The prime factors of 12 are 2, 2, and 3. This is because 2 * 2 * 3 = 12 and both 2 and 3 are prime numbers.

One way to calculate prime factors is to pull out the smallest prime number and then do the same thing with the results.

We'll use the first few prime numbers: 2, 3, 5, 7, and 11.

Let's get the prime factors of 12:

1. Does "2" divide evenly into 12? (Yes)
2. Add "2" to our list of factors.
3. 12 / 2 = 6
4. Does "2" divide evenly into 6? (Yes)
5. Add "2" to our list of factors (again).
6. 6 / 2 = 3
7. Does "2" divide evenly into 3? (No)
8. Does "3" divide evenly into 3? (Yes, it's a prime)
9. Add "3" to our list of factors.

In taking this, our factors are 2, 2, and 3.

Calculating Prime Factors Programatically
When I was originally working on Euler #3, I was thinking if there was a way to use this methodology to create a function. I wasn't happy with the solutions that I came up with because they were very procedural in nature.

One of the solutions that I came across online was from Mark Heath (Finding Prime Factors in F#). Here's his solution:

It does work, but when I first ran across it, I didn't want to take the time to try to understand it. (The value names put me off a bit since they weren't very helpful.)

I went back to it (since I needed real prime factorization for Euler #5). This code does exactly what I did in the manual process above.

Here's the same code with some different value names:

"getFactor" is a recursive function that uses an accumulator to store the prime factors. The "primeFactors" function kicks off the call to "getFactor" with some initial values.

Let's walk through this with our value of "12".

First Call
The first call look like this: getFactor 12 2 []. Our target number is 12, the current proposed factor is 2 (the smallest prime number), and our accumulator is an empty list.

Since our proposed number (2) is not equal to our target number (12), the "if" conditional returns false.

The "elif" conditional returns true: 12 % 2 = 0 (since 12 is evenly divisible by 2). Then we end up calling the function recursively.

Second Call
The second call looks like this: getFactor (12/2) 2 (2::[]). When we do some evaluation, we end up with getFactor 6 2 [2].

Since our proposed number (2) is not equal to our (new) target number (6), the "if" conditional returns false.

The "elif" conditional returns true: 6 % 2 = 0. So we end up calling the function recursively again.

Third Call
The third call looks like this: getFactor (6/2) 2 (2::[2]). Which evaluates to getFactor 3 2 [2; 2].

Since our proposed number (2) is not equal to our target number (3), the "if" conditional returns false.

The "elif" also returns false: 3 % 2 does not equal 0.

So we end up in the "else" where we call the function recursively again.

Fourth Call
The fourth call looks like this: getFactor 3 (2+1) [2; 2]. Which evaluates to getFactor 3 3 [2; 2].

The "if" conditional returns true since our (new) proposed number (3) equals our target number (3). So this results in 3::[2; 2]. And this can be re-written as [3; 2; 2].

And since this is the last value in our function call, this is what gets returned.

A Bit of Rewriting
I like to use local functions (I'm not sure why, but it feels right for the time being). So my final form of this function looks like this:

I think the reason I'm more comfortable with a local function in this case is because it doesn't make sense to call "getFactor" with anything but the starting values of "2" for the proposed number and an empty list for the accumulator. Wrapping it in the "primeFactors" function prevents someone from using it inappropriately.

If "getFactor" was a more general-purpose function (or even useful in more than one scenario), then I would probably keep it separate here.

Updating Euler Problem #3
This new function actually makes Euler Problem #3 pretty trivial. All we need to do is calculate the prime factors (which we can do here) and pick out the largest value.

But since our target number is bigger than a 32-bit integer, we'll need to make this work with bigger numbers.

Here's the final code:

By adding "L" to all of our integers, the type inference system now knows that we're working with 64-bit integers (and we can see that in the output).

The last step is a call to "List.max" to get the largest value out.

When we try this with the sample number...

We see that we get the expected result of "29".

And when we try this with our target number...

We also get the expected result. And even better, with timing turned on, we see that this took almost no time at all to complete. So our performance is much better than our brute force approach.

Wrap Up
Sometimes we can learn just as much from taking apart some else's code as we can from writing the code ourselves. And that's what I did here. I didn't write the recursive function; instead, I found someone who had written one.

It took me some time to figure out what the code was doing. But when I did, I saw that it was calculating prime factors exactly the same way as when I was doing it manually.

More exploration to come...

Happy Coding!