h4ck3r.net

Euler 3

11 May 2008

The problem statement:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143?

The first thing we need to do likely is know if a number is prime:

let isprime x =
    x > 1 &&
    not(Seq.exists (fun n -> x % n = 0) {2..int(sqrt (float x))})

This is a little sneaky. First, it generates a list of numbers from 2 to the square root of the number to be tested (square root because the largest possible factor). Then, it uses an existence test to see if any of those numbers can divide into the candidate number. If they can, we know it’s not prime.

With that out of the way, we can attack the actual problem. My first attempt was very C-like, to whit:

let prob3 num = 
    for i = int(sqrt(float num)) to 2 do
        if num % int64 i = 0L && isprime(i) then return i
prob3 600851475143L

But, that doesn’t work. ‘return’ doesn’t exist, and the type of ‘for’ is unit, so there’s no way to get the result out. I was trying to avoid computing too many results, so going backwards was the goal (rather than making a list of answers and filtering them, as in the previous problems).

I didn’t exactly figure out how to do that, but I did come up with a reasonable solution (at least to my non-F# eyes):

let num = 600851475143L
{ for i in [2..int(sqrt(float num))] do
    if num % int64 i = 0L && isprime(i) then yield i }
|> Seq.fold(fun a x -> max a x) 0

First, we make a list of all the factors of the target number that are also prime (the comprehension). Then, fold the maximum value out of those. It’s definitely doing a lot more work than necessary, but it works OK.

There’s also a little bit of mucking around in this problem because the number was bigger than 2^32-1. F# handles it reasonably cleanly though, at least up to int64 range, by just adding some float/int/int64 calls to convert things to the right types explicitly. Not sure what bignum looks like yet though.