There are a number of sieve algorithms that can be used to list prime numbers up to a certain value.  I came up with this implementation in Scala. I rather like it, as it makes no use of division, modulus, and only one (explicit) multiplication.
Despite being in Scala, it’s not in a functional style. It uses the awesome mutable BitSet data structure which is very efficient in space and time. It is intrinsically ordered and it allows an iterator, which makes jumping to the next known prime easy. Constructing a BitSet from a for comprehension is also easy with breakOut.
The basic approach is the start with a large BitSet filled will all odd numbers (and 2), then iterate through the BitSet, constructing a new BitSet containing numbers to be crossed off, which is easily done with the &~= (and-not) reassignment method. Since this is a logical bitwise operation, it’s blazing fast. This code takes longer to compile than run on my oldish MacBook Air.
import scala.collection.mutable.BitSet import scala.collection.breakOut
println(new java.util.Date()) val top = 200000
val sieve = BitSet(2) sieve |= (3 to top by 2).map(identity)(breakOut)
val iter = sieve.iteratorFrom(3)
while(iter.hasNext) {
val n = iter.next
sieve &~= (2*n to top by n).map(identity)(breakOut)
}
println(sieve.toIndexedSeq(10000)) // 0-based println(new java.util.Date())
As written here, it’s a solution to Euler #7, but it could be made even faster for more general use.
For example
- I used a hard-coded top value (which is fine when you need to locate all primes up to  n). For finding the nth prime, though, the top limit could be calculated
- I could stop iterating at sqrt(top)
- I could construct the removal BitSet starting at n*n rather than n*2
I suspect that spending some time in the profiler could make this even faster. So take this as an example of the power of Scala, and a reminder that sometimes a non-FP solution can be valid too. Does anyone have a FP equivalent to this that doesn’t make my head hurt? :-)
-m