Prime factorization in F#

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  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()

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 overnigh

(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()
    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

StackExchange Code Review Q#114228, answer score: 7