[erlang-questions] generating primes
Imre Palik
imre@REDACTED
Tue Oct 14 10:46:03 CEST 2008
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
More information about the erlang-questions
mailing list