5
\$\begingroup\$

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 []
\$\endgroup\$
  • \$\begingroup\$ Hint - use the mod operator (%) \$\endgroup\$ – John Palmer Nov 5 '14 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\$ – Overly Excessive Nov 5 '14 at 22:34
1
\$\begingroup\$

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

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 []
\$\endgroup\$
  • \$\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 '18 at 15:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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