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

[Matthias Lang]

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