Problem 3 of the Euler Project is:

Find the largest prime factor of a composite number.

As previously mentioned, having a lazy prime generator is kind of nice when it's time to solve this problem. The idea I settled on is to create a prime factorization of the target number. From that list I can then select the largest prime factor.

Here's my prime factorization code:

let rec factors n = 
    let root (n:int64) =
        int64 (sqrt (float n))
    let rec exp e p n =
        match n%p with
        | 0L -> exp (e+1L) p (n/p)
        | _  -> e
    let rec pow e p =
        match e with
        | 0L -> 1L
        | e  -> p*pow (e-1L) p  
    let primes = sieve 2L Map.empty
    seq {
        if n > 1L then
            let divisor = primes |> Seq.takeWhile (fun k -> k <= root n) |> Seq.tryFind (fun k -> n%k = 0L)
            match divisor with
            | None      -> yield (n, 1L)
            | Some(k)   ->
                let e = exp 0L k n
                yield (k, e)
                yield! factors (n/pow e k)
    }

I think this looks more complicated than it actually is because of the embedded helper functions: the root function computes the square root of an integer, exp computes the number of times a prime number appears in the prime factorization of a composite number and pow raises an integer to a power. It's not clear to me whether it would be better to have these as standalone functions or as embedded ones.

The result of passing a number into factors is a sequence of tuples where the first entry is the prime factor and the second is the number of times that factor goes into the composite number. This function will come in useful in my solutions to later Project Euler problems.

With this factorization function the solution to the problem is:

factors 600851475143L |> Seq.map (fun k -> fst k) |> Seq.max |> printfn "%A"

The mapping step basically throws away the exponent and allows us just to focus on the prime factor.

There is a some inefficiency in this code. Every time factors is called recursively it starts checking prime factors from the very first prime. Yet we know that we've already checked some of them previously. I briefly messed around with fixing this by always pulling from the same sequence of primes rather than creating a new one every time. Then I decided it was more trouble than it was worth.