Yan Cui
I help clients go faster for less using serverless technologies.
This article is brought to you by
Don’t reinvent the patterns. Catalyst gives you consistent APIs for messaging, data, and workflow with key microservice patterns like circuit-breakers and retries for free.
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
Whenever you’re ready, here are 3 ways I can help you:
- Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
- I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
- Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.
Pingback: Project Euler — Problem 7 Solution | theburningmonk.com
Pingback: Project Euler — Problem 10 Solution | theburningmonk.com
Pingback: Project Euler — Problem 12 Solution | theburningmonk.com
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
?
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
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.
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)
Ding! Yes, I missed Seq.collect, was trying and failing to get Seq.map to do something similar. Thanks again.
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.
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