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 []

• John Palmer: Hint - use the mod operator (%)
• Overly Excessive: @JohnPalmer That would have created more code because the modulus operator only returns the remainder of a divison while Math.DivRem will return both the remainder and the quotient as a tuple in F#.

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"

• Carcigenicate: F# has nested guards? Haskell really needs this :(
• mattnewport: A match is just an expression in F#. I don't really know Haskell (on my list to learn!) but I think a match expression is a bit like a case in Haskell.
• Carcigenicate: OK then, nevermind. Cases can be nested. And I recommend learning Haskell; it's a very neat language.
• ntohl: It could go till the sqrt of n

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 []

• ntohl: For me it's failing for test case 8L> [<TestCase(8L, [|2L; 2L; 2L|])>] | let prime_factors_of_number number expect = | primeFactors number |> should equal expect