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

[Imre Palik]

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

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

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).
{start,{1233,938342,764000}}
{p1,{1233,938385,702000}}
{p2,{1233,938441,827000}}
true
16> prime_test:run(10000000).
{start,{1233,938718,296000}}
{p1,{1233,938760,608000}}
{p2,{1233,938816,702000}}
true
17> prime_test:run(10000000).
{start,{1233,938821,827000}}
{p1,{1233,938864,30000}}
{p2,{1233,938919,952000}}
true
18>


Ι.

I.