Project Euler Problem 3 in F#
2010 July 1
Continuing with my journey learning F# I have tackled Project Euler problem number 3, which asks:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143
This problem deals with the fascinating problem of prime numbers factorization, which is considered a hard problem. So hard that our current cryptography schemes rely on this property.
This is my solution:
#light
open System
let is_prime x =
let rec check i =
double i > sqrt (double x) || (x % i <> 0L && check (i + 1L))
check 2L
let big_number_factors n =
let factors = seq {
let limit = n / 2L
for i in 2L .. limit do
if n % i = 0L && is_prime i then yield i }
Seq.max factors
A few comments:
- The first function (
is_prime) is a simple trial division to determine whether a given number is prime. There are cleverer algorithms to find prime numbers: see for example here For an interesting discussion you can also have a look at The Genuine Sieve of Erathostenes by Melissa O’Neill. - The second function uses comprehension to create the list of primes which are factors for the input value. At the end we simply return the biggest factor.
I’m afraid your function is not doing what it suppose to do.
In your “max_factor” funciton you’re only testing numbers up to sqrt(n), but prime factors can be > that.
For example prime factors of 2010 are [2;3;5;67] but because 67 > sqrt(2010)//44.8 your function would return 5 as a max factor, which is obviously wrong.
Square root is the limit when testing if a number is prime and you can use it in the “is_prime” function instead of (i>x/2):
let isPrime x =
let rec check i =
double i > System.Math.Sqrt(double x) || (x % i 0I && check (i + 1I))
check 2I
Best regards
Good catch, Jakub. For some reason I had swapped the two limits between the two functions (and still had my algorithm working for this particular case).
I am updating the code accordingly, while also moving from BigInteger to long which is enough for this case and it’s much quicker at run time.