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 []
  • \$\begingroup\$ Hint - use the mod operator (%) \$\endgroup\$ Nov 5, 2014 at 22:30
  • 1
    \$\begingroup\$ @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#. \$\endgroup\$ Nov 5, 2014 at 22:34

2 Answers 2


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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.