[erlang-questions] beginner: Generating a list of prime numbers

Imre Palik imre@REDACTED
Fri Feb 6 17:49:07 CET 2009

Feladó: Bjorn Gustavsson [bgustavsson@REDACTED]
> On Fri, Feb 6, 2009 at 12:23 PM, Imre Palik <imre@REDACTED> wrote:
>> The real morale of the thing is that you want to use list comprehension whenever you can.  It tends to be much faster than recursion.
> That surprises me, because I happen to know how list comprehensions
> are implemented.
> Do you have any measurements to back up your statement?

Here it is:

% code start here


sieve1([H|T], S) when H =< S -> [H|sieve1([X||X<-T, X rem H /= 0], S)];
sieve1(L, _) -> L.

filter(_, [], A) -> lists:reverse(A);
filter(P, [H|T], A) when H rem P == 0 -> filter(P, T, A);
filter(P, [H|T], A) -> filter(P, T, [H|A]).

sieve2([H|T], S) when H =< S -> [H|sieve2(filter(H, T, []), S)];
sieve2(L, _) -> L.

run(N) ->
    erlang:display({start, now()}),
    P1 = sieve1(lists:seq(3, N), math:sqrt(N)),
    erlang:display({p1, now()}),
    P2 = sieve2(lists:seq(3, N), math:sqrt(N)),
    erlang:display({p2, now()}).

% code ends here

15> prime_test:run(10000000).
16> prime_test:run(10000000).
17> prime_test:run(10000000).



More information about the erlang-questions mailing list