Project Euler 3: Getting the largest prime factor of a number

Question

I'm looking for some general feedback on my solution to Project Euler challenge 3

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

let p3 () = 
    let rec primeFactors n i primes = 
        if i > n/2L then n::primes else
            let quotient, remainder = Math.DivRem(n, i)
            if remainder = 0L then primeFactors quotient 2L (i::primes)
            else primeFactors n (i + 1L) primes
    primeFactors 600851475143L 2L []

Answer 1

There's nothing really wrong with your code but here's a slight rewrite using pattern matching which is arguably a more functional style than if ... then ... else. I also rearranged the args to eliminate the unnecessary n parameter on the outer function.

let primeFactors = 
    let rec recPrimeFactors primes i = function
        | n when 2L*i > n -> n::primes
        | n -> match n % i with
               | 0L -> recPrimeFactors (i::primes) 2L (n / i)
               | _ -> recPrimeFactors primes (i + 1L) n
    recPrimeFactors [] 2L

600851475143L |> primeFactors |> List.head |> printfn "%d"

Answer 2

There is inefficiency due to a simple strategic blunder: if remainder = 0L, then there is no reason to re-test all candidate factors starting from 2 again. You can just continue with primeFactors quotient i (i::primes).

The only possible even prime factor is 2, so you only need to test the odd numbers.

I'd also restructure the tests into one pattern match, because your nested if-else is a bit hard to read, especially the way you have placed the line breaks inconsistently.

let p3 =
    let rec primeFactors (n: int64) (i: int64) primes =
        let quotient, remainder = Math.DivRem(n, i)
        match remainder with
            | 0L               -> primeFactors quotient i (i::primes)
            | _ when i + i > n -> n::primes
            | _ when i = 2L    -> primeFactors n 3L primes
            | _                -> primeFactors n (i + 2L) primes
    primeFactors 600851475143L 2L []