# [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
machine:

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
{ok,prime_test}
2> prime_test:run(10000000).
{start,{1233,954836,637538}}
{p1,{1233,954948,700238}}
{p2,{1233,955063,218981}}
true

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).
{start,{1233,955375,697367}}
{p1,{1233,955488,314905}}
{p2,{1233,955603,458047}}
{p3,{1233,955717,964138}}

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

3> prime_test:run(10000000).
{start,{1233,955391,95580}}
{p1,{1233,955426,572019}}
{p2,{1233,955465,160014}}
{p3,{1233,955503,541756}}

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

Matt

----------------------------------------------------------------------
-module(prime_test).
-export([run/1]).

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()}).

```