[erlang-questions] generating primes
Tue Oct 14 10:46:03 CEST 2008
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() -> ;
[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?)?
More information about the erlang-questions