Mark Pearl

So this weekend I made an attempt at problem 3 of Project Euler.

Problem 3

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

What is the largest prime factor of the number 600851475143 ?

My Solution

// Checks whether a number is prime or not using the Trial Division approach
// To improve performance I have only pass through odd numbers greater than 2 and do not check for this case
let isPrime (number : bigint) =
    match number with        
        | _ -> seq { bigint(2) .. bigint(1) .. bigint (Math.Sqrt (float number))}    
                |> Seq.exists (fun x -> if (number % x = bigint(0)) then true else false)      
                |> not        

// Returns a sequence of prime numbers up to number x
let primenumbersOf (number : bigint) =    
    let oddPrimes = seq { bigint(3).. bigint(2) .. number} |> Seq.filter(fun x -> isPrime x)                
    Seq.append [bigint(2)] oddPrimes

// Returns a sequence of prime factors of a specific number x
let primefactornumbersOf (number : bigint) =
    primenumbersOf (number / bigint(Math.Sqrt(float(number))))    
    |> Seq.filter(fun x -> number % x = bigint(0))

primefactornumbersOf(bigint(600851475143.0)) |> Seq.iter (fun x -> Console.WriteLine(x))

It works fine except it is not the most performant approach. I would appreciate any feedback from people that could maybe help me look at a different approach that would return a quicker result.

blog comments powered by Disqus

Want to get my personal insights on what I learn as I learn it? Subscribe now!