Project Euler Problem 3 in F#

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:

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.