Prime factorization in F#
(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 
|&gt; Seq.map(fun a -&gt; (int (number/(int64 a))))
|&gt; Seq.iter(addBigPrime)

let answer = smallPrimes |&gt; Seq.append(bigPrimes) |&gt; Seq.max


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

let answer = smallPrimes 
             |&gt; getBigPrimes
             |&gt; 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&lt;int&gt;()
    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 |&gt; 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