generating primes

[ImRe]

Could anybody point me to a purely functional algorithm that generates primes efficiently? Currently I tend to use the following erlang implementation of the sieve of Erathostenes:

Code: Select all

sieve([]) -> [];
sieve([H|T]) -> [H|sieve([X||X<-T,X rem H =/= 0])].

But it tends to be slow if one needs lots of primes.

[jaap]

It seems to me that
X rem H =/= 0
is testing x for divisibility by H, and actually performs the division. Most implementations of Eratosthenes' sieve instead use repeated addition. In other words, cross of 2H as being composite, add H to get 3H, cross of 3H as being composite, add H to get 4H, etc. Even better is to not store even numbers at all and just cross of 3H, 5H, 7H, ... instead.
I don't know my Erlang from my elbow, so I can't tell how difficult it would be to express this idea in it.

[quilan]

I found a link to a dozen prime-sieve modules for haskell a while back, but I'd have to be at work to find them again. I'll see what I can find tomorrow.

[daniel.is.fischer]

http://www.haskell.org/haskellwiki/Prime_numbers has several, some more efficient than others. Depending on what to accomplish, my favourites are the implicit heap and a bitsieve.

[Ikcelaks]

One natural method of writing the Eratosthenes' sieve functionally is to write the common array-based algorithm in such a way that the array is used linearly. This is very natural to do, and very efficient. As you work your way through the numbers, add each prime to an accumulation list and return that final list as your function's result. Now, even though you are using a mutable array, by virtue of the linear usage, it's just the same as using persistent vectors, except that you're taking advantage of the fact that you no longer have references to the old vectors to justify updating in place. So you can see how this is a functional implementation from a philosophical perspective. Some languages will enforce this pattern of usage with their type-system. Others (like SML) are impure, so you just use programmer discipline.