theburningmonk.com

Prob­lem

The prime fac­tors of 13195 are 5, 7, 13 and 29.

What is the largest prime fac­tor of the num­ber 600851475143 ?

Solu­tion

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 solu­tion requires a bit more work, I cre­ated two helper func­tions find­Fac­tor­sOf and isPrime, and as you’ve prob­a­bly noticed, I had explic­itly declare that the value n should be a int64 type:

let findFactorsOf(n:int64)

That’s because the num­ber 600851475143 in the prob­lem is out­side of the range of the int32 type so all the func­tions must be able to work with a int64 type. This is one of few cases where you can’t just rely on the type infer­ence in F#.

Another thing you might have noticed is that the syn­tax for cast­ing in F# is type(value), e.g.

int64(n)

as opposed to the syn­tax in C#:

(long)n

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

open System

which is equiv­a­lent to the using direc­tive in C#:

using System