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

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

• Hint - use the mod operator (%) – John Palmer Nov 5 '14 at 22:30
• @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#. – Overly Excessive Nov 5 '14 at 22:34

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"

• F# has nested guards? Haskell really needs this :( – Carcigenicate Nov 6 '14 at 12:29
• 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. – mattnewport Nov 6 '14 at 16:12
• OK then, nevermind. Cases can be nested. And I recommend learning Haskell; it's a very neat language. – Carcigenicate Nov 6 '14 at 19:34
• It could go till the sqrt of n – ntohl Mar 7 '18 at 15:35

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

• 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 – ntohl Mar 7 '18 at 15:20