Greatest Prime Factor in F#

Today I was reading an article in The Onion, Conquerors You May Have Missed, and noticed that the number for the ant looked like it might be a big old prime, or at least have a large prime divisor. (For reference, the ant is # 43,168,974,563,247.) There are a number of algorithms for finding this answer, but my favorite is a little brute force algorithm that keeps dividing the big number by some other value until the two numbers are equal. Yes, I know I can short circuit a bunch of testing via a square root function, but BigInteger doesn’t have a sqrt function (yet…).

Anyhow, I cobbled this together and it worked right out of the gate:

let rec largestFactor x y = if (x = y) then y else let z = x % y if z = 0I then largestFactor (x/y) y else largestFactor x (y + 1I) let LargestPrime x = largestFactor x 2I let a = LargestPrime 43168974563247I printf "%A" a

Answer: 84,826,177

So, the number isn’t prime, but the largest prime factor is pretty big! And, writing up the code to figure out the answer itself was pretty simple.

Posted 12-16-2009 6:00 PM by Scott Seely

[Advertisement]