[erlang-questions] generating primes

[Imre Palik]

Hi,

I am playing with Project Euler nowdays, and in the last few problems I solved I had problems generating primes fast enough.  Currently I am using the following implementation of the Sieve of Eratosthenes:

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

I tried to change it to use addition instead of doing the remainder:

sieve_filter(_, _, []) -> [];
sieve_filter(F, I, [F|T]) -> sieve_filter(F + I, I, T);
sieve_filter(F, I, [H|T]) when H > F-> [H|sieve_filter(F + I, I, T)];
sieve_filter(F, I, [H|T]) -> [H|sieve_filter(F, I, T)].

sieve2([]) -> [];
sieve2([H|T]) ->
    [H|sieve2(sieve_filter(3 * H, 2 * H, T))].

But this one runs slower than the original.  Could anybody explain why?  Are there any optimisations I can do here, or do I have to find a better algorithm (any pointers?)?

Thanks

Imre