Prime factorization in F#

Question

In the pursuit of learning F#, I have been working through some Project Euler problems.

This is my solution for problem 3:

open System
open System.Collections.Generic
let number = 600851475143L
let limit = Convert.ToInt32(sqrt (float number))
let sieve = Array.create (limit+1) true
sieve.SetValue(false,0)
sieve.SetValue(false,1)
let rec markNotPrime prime multiple =
 if multiple > limit then prime
 else
 sieve.SetValue(false, multiple)
 let nm = prime+multiple 
 markNotPrime prime nm
let smallPrimes = 
 Seq.unfold(fun a -> Some(a, (a+1))) 2
 |> Seq.takeWhile(fun a -> a <= limit)
 |> Seq.filter( fun a -> sieve.[a])
 |> Seq.map( fun a -> 
 let b = a+a
 markNotPrime a b)
 |> Seq.filter( fun a -> number % (int64 a) = 0L)
let bigPrimes = new List<int>()
let rec addBigPrime potentialPrime = 
 match potentialPrime with
 | p when bigPrimes.Contains(potentialPrime) -> 
 ignore()
 | p when smallPrimes |> Seq.forall(fun a -> (potentialPrime % a) <> 0) -> 
 bigPrimes.Add(p)
 | _ -> 
 smallPrimes 
 |> Seq.filter(fun a -> 
 (potentialPrime % a) = 0) 
 |> Seq.iter(fun a -> 
 addBigPrime (potentialPrime / a))
smallPrimes 
 |> Seq.map(fun a -> (int (number/(int64 a))))
 |> Seq.iter(addBigPrime)
let answer = smallPrimes |> Seq.append(bigPrimes) |> Seq.max
printfn "smallPrimes: %A" smallPrimes
printfn "bigPrimes: %A" bigPrimes
printfn "answer: %d" answer

I am aware of how simply this could have been done, but I was trying to do this in a vacuum as much as possible.

I am new to both prime factorization and F#; however, I am really only looking for comments on F#, not how poorly my factorization algorithm works (I know it's bad) i.e. what style mistakes am I making, or how the code could be made more functional.

Of particular interest, where do you think I am missing the mark entirely?

Update

After thinking more about my solution overnight, I had more thought about exactly what my solution was doing, and why the simpler methods are so much simpler.

During my research on factoring primes, I think I got too caught up in the sieve of Eratosthenes, and didn't focus on the actual problem.

What I should have been trying to do:

1. Search for the smallest prime factor
2. Once found save it to the list of prime factors
3. Divide this factor out of the number to be factored
4. Repeat from step 1 substituting the number to be factored with the quotient from step 3, and start the search from the prime factor found in step 2.
5. Get the biggest prime from the list.

What I actually did:

1. Search for all prime numbers from 2 to the square root of the number to be factored.
2. During the search, check each prime to see if it divides evenly.
3. Once complete divide each of these "small primes" to generate a list potential big primes.
4. Divide each of the big primes by all of the small primes as a test for primality.
5. Combined the lists, and get the biggest one.

Answer 1

(Apologies in advance for any bad F# syntax in this answer)

One issue is that you're doing things statefully. In a functional style, you want functions to be pure, as much as possible- i.e. their purpose is to return something, not to change state. Whereas you have global collections like sieve and bigPrimes, and functions whose purpose is to modify those collections.

Taking the last part in particular, you do:

smallPrimes 
|> Seq.map(fun a -> (int (number/(int64 a))))
|> Seq.iter(addBigPrime)
let answer = smallPrimes |> Seq.append(bigPrimes) |> Seq.max

Instead, you want to be able to do something like:

let answer = smallPrimes 
 |> getBigPrimes
 |> Seq.max

In this case getBigPrimes would just calculate the big primes from the small ones, probably using a recursive inner function. A useful technique to allow you to do this without any state mutation is to have an accumulator collection as a parameter to your recursive function (often called acc). Then instead of having some list you repeatedly add results to, you pass a new acc to each call of the recursive function, created by prepending the result to the previous one acc.

So as an example, instead of:

let primesUpTo n = 
 let primes = new List<int>()
 let rec loop i =
 if isPrime n primes then primes.Add(n)
 if i = n then primes else loop i+1
 loop 2

You'd do:

let primesUpTo n =
 let rec loop i acc =
 if i = n then acc
 elif isPrime i acc then loop i+1 i::acc
 else loop i+1 acc

Notice that by replacing iteration with this tail recursive style, you no longer have to have mutable state in the form of a collection which gets updated. This (and the fact that recursive algorithms often read as more declarative than iterative ones), mean that tail recursion is generally preferred over iteration in F#.

---

As you already said in your question, your algorithm is a bit strange. Your alternative algorithm is much better. Writing it in the same recursive style, an outline would look something like:

let rec largestFactor n primes =
 let factor = smallestFactor n primes
 if factor = n then factor else largestFactor n/factor primes
let answer = primesUpTo n |> largestFactor n

You'd then just need to implement primesUpTo (which you'd want to make lazy, so that you don't calculate primes higher than you need) and smallestFactor

• Luke Cummings: Thanks a lot, very clear. I think I get all this, but one more concern I had was about the recursion. I have been reading about tail recursion and was just wondering if there was any reason to address it as it applies to this example? Like perhaps are there any gotchas I would want to know about when applying this recursive style.
• Ben Aaronson: @LukeCummings Not that I'm aware of. Using tail recursion is very F# idiomatic, and the language ensures that it won't lead to stack overflows
• Der Kommissar: @BenAaronson You should consider explaining that tail recursion in F# tends to be preferred over loops.
• Ben Aaronson: @EBrown I added an extra paragraph that hopefully makes this more explicit