This one required a flash of inspiration. We recursively build a list of prime factors by finding the first even divisor j of n, necessarily prime, and then repeating with n/j until we reach n = 1. It works out that the head of the list is the largest prime factor.
let problem3a = let factorize n = let rec factorize n j list = if n = 1I then list elif n % j = 0I then factorize (n/j) j (j::list) else factorize n (j + 1I) (list) factorize n 2I [] 600851475143I |> factorize |> List.head
Now, we only need the largest prime factor so this algorithm can be specialized.
let problem3b = let rec largestFactor n j largest = if n = 1I then largest elif n % j = 0I then largestFactor (n/j) j j else largestFactor n (j + 1I) largest largestFactor 600851475143I 2I 1I
No need for bigintegers here! They harm performance. An Int64 will swallow our number easily. An Int64 goes up to 19 figures (over 9 quadrillion), and we've only got 12 figures here. By suffixing numbers above with 'L' instead of 'I', everything zips along much faster.
ReplyDeleteAlso, if start our primes on 3 instead of 2, we can avoid checking for even numbers altogether by adding 2 instead of 1 to the next candidate factor. Here was my solution:
let rec prime n i =
... if n <= i then n
... elif n%i = 0L then prime (n/i) i
... else prime n (i+2L)
prime 600851475143L 3L