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

Matthias Lang <>
Fri Feb 6 22:51:14 CET 2009

On Friday, February 06, Imre Palik wrote:

Imre> >> The real morale of the thing is that you want to use 
Imre> >> list comprehension whenever you can.  It tends to be 
Imre> >> much faster than recursion.

I see no big difference between code variants when running on my

  Erlang (BEAM) emulator version 5.6.5 [source] [64-bit] [smp:2] [async-threads:0] [hipe] [kernel-poll:false]
  Eshell V5.6.5  (abort with ^G)
  1> c(prime_test).
  ./prime_test.erl:16: Warning: variable 'P1' is unused
  ./prime_test.erl:18: Warning: variable 'P2' is unused
  2> prime_test:run(10000000).

I tried adding a plain recursive version of filter (see code below),
but didn't get any significant differences there either:

  19> prime_test:run(10000000).               

Repeating on a 32-bit version of R11B-5 on a different machine didn't
produce anything spectacular either:

  3> prime_test:run(10000000).

Aside: that call to lists:seq(3, N) looks suspicious.



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]).

rfilter(P, [H|T]) when H rem P == 0 -> rfilter(P, T);
rfilter(P, [H|T]) -> [H|rfilter(P,T)];
rfilter(_, []) -> [].

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

sieve3([H|T], S) when H =< S -> [H|sieve3(rfilter(H, T), S)];
sieve3(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()}),
    P3 = sieve2(lists:seq(3, N), math:sqrt(N)),
    erlang:display({p3, now()}).

More information about the erlang-questions mailing list