Getting Prime Numbers up to 1,000,000 using F#

In a previous blog, I wrote how to get all the prime numbers from 1 to 1,000,000 using C# and LINQ technology.  This blog shows you how to do the same thing in F# without using LINQ at all.  

A lot of what LINQ gives you is already built into F#, so you don't really need it.  The collection functions in F# come with functions that operate on predicates just like LINQ.  For example, the filter function in F# list collections are the same as using a WHERE clause in LINQ.  Linq is just a little bit easier to understand and less hassle if you already know C#.  But look at the equivalent code in F#.  It's only a few lines!

// open the system namespace of .NET
open System;

// assign the upperbound
let x = 1000000;;

// we only need the square root of the upper bound to eliminate factors
let upperBound = Convert.ToInt32(Math.Sqrt(Convert.ToDouble(x)));;

// get a reference to a list of all integers from 1 to 1,000,000
// (in other words, get a mutable list)
let allNumbers = ref [1..x] in

// loop through all numbers from 1 to the square root of 1,000,000.
// keep removing numbers that have more than 1 factor
for div = 2 to upperBound do
 
allNumbers := List.filter(fun num -> (num % div <> 0 or div >= num))
        !
allNumbers
done;

// print out the results
print_any(allNumbers);;

Note that the techniques used in this article are very similar to those already described by Matt in the lazy evaluation of primes with C#.

Ebook Download
View all
Learn
View all