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
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
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.
12-16-2009 6:00 PM