Saturday, May 8, 2010

Problem 3: What is the largest prime factor of the number 600851475143?

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

1 comment:

  1. 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.

    Also, 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

    ReplyDelete