Project Euler – Problem 3 Solution

Problem

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution

open System

let findFactorsOf(n:int64) =
    let upperBound = int64(Math.Sqrt(double(n)))
    [2L..upperBound] |> Seq.filter (fun x -> n % x = 0L)

let isPrime(n:int64) = findFactorsOf(n) |> Seq.length = 0

let findMaxPrimeFactorOf(n:int64) =
    let upperBound = int64(Math.Sqrt(double(n)))

    [2L..upperBound]
    |> Seq.filter (fun x -> n % x = 0L)
    |> Seq.filter isPrime
    |> Seq.max

let maxPrime = findMaxPrimeFactorOf(600851475143L)

As this solution requires a bit more work, I created two helper functions findFactorsOf and isPrime, and as you’ve probably noticed, I had explicitly declare that the value n should be a int64 type:

let findFactorsOf(n:int64)

That’s because the number 600851475143 in the problem is outside of the range of the int32 type so all the functions must be able to work with a int64 type. This is one of few cases where you can’t just rely on the type inference in F#.

Another thing you might have noticed is that the syntax for casting in F# is type(value), e.g.

int64(n)

as opposed to the syntax in C#:

(long)n

And did you notice that I used the Math.Sqrt method in my solution? That’s right, you can use any CLR types in F# just as you can in C#! In order to import a namespace in F#, you need to use the open keyword:

open System

which is equivalent to the using directive in C#:

using System
  • Pingback: Project Euler — Problem 7 Solution | theburningmonk.com()

  • Pingback: Project Euler — Problem 10 Solution | theburningmonk.com()

  • Pingback: Project Euler — Problem 12 Solution | theburningmonk.com()

  • Matt1970

    First, thanks for posting these solutions. Very useful to F# beginners like me.

    Is there a reason you are not reusing findFactorsOf in findMaxPrimeFactorOf, so that findMaxPrimeFactorOf becomes

    let findMaxPrimeFactorOf(n:int64) =
    findFactorsOf(n)
    |> Seq.filter isPrime
    |> Seq.max

    ?

  • Yan Cui

    Hi Matt, there’s absolutely no reason why I shouldn’t have reused it. Looking at it now, it’s an obvious oversight!

    On a side note, the isPrime function here is very naive, and for later problems I started to use a sieve. which on my machine was able to generate all the primes under 1,000,000 in under a second. You might find it useful for some of the later prime number related problems too.
    See:
    https://github.com/theburningmonk/ProjectEuler-FSharp-Solutions/blob/5b2f10b199010dcdf2d94be5804b1f6da2916395/ProjectEulerSolutions/ProjectEulerSolutions/Common.fs#L27-L40

  • Matt1970

    There’s actually a bug in the above, findFactorsOf isn’t finding all the factors, only part of them. If you run findMaxPrimeFactorOf(15L) you’ll get 3 instead 5. In the Euler problem all the factors are Seq.filter (fun x -> n % x = 0L)
    seq {
    for x in partialFactors do
    yield x
    yield n / x
    }

    Thanks for the pointer to the sieve. Don’t understand it yet, but I’ll study it more. I see some prime number sieves on Wikipedia.

  • Yan Cui

    aha, yup, you’re right! Thanks for pointing that out :-)

    Alternatively, you can also write:
    [2L..upperBound]
    |> Seq.filter (fun x -> n % x = 0L)
    |> Seq.collect (fun x -> [ x; n/x ])

    (collect works the same way as LINQ’s SelectMany)

  • Matt1970

    Ding! Yes, I missed Seq.collect, was trying and failing to get Seq.map to do something similar. Thanks again.

  • http://rianjs.net Rian

    Any reason you didn’t generate the sequence from highest to lowest, decrementing by 2 so you only get odd numbers to further reduce the search space? (After handling the odd vs even starting point.)


    [upperBound .. -2L .. 3L] |> //etc.

    And then call Seq.head instead of Seq.max. I think Seq.head should cause execution to halt after the first element is returned, rather than evaluating the entire search space(?). I decompiled the result, and it seems this is true, though I’m not sure how SeqModule.Filter works behind the scenes.

  • precogtyrant

    i was thinking the same. i am just learning f# btw so not an expert. i didn’t generate it from highest to lowest but just used Seq.last instead of max.

    open System
    let num = 600851475143L
    let findfactors(n:int64) =
    let upper = int64(Math.Sqrt(double(n)))
    {2L..upper} |> Seq.filter(fun x -> n % x = 0L)

    let isprime(n:int64) = findfactors(n) |> Seq.length = 0

    findfactors(num) |> Seq.filter(fun x -> isprime(x)) |> Seq.last