Sieve of Eratosthenes in Erlang I just started learning Erlang. Here is my crack at the Seive, based on (https://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf):

-module(seive).
-export([seive/1]).

seive(N) -&gt;
    L = lists:seq(1,N),
    {Megass, Ss, Micros} = erlang:timestamp(),
    S = doseive(L, 2),
    {Megase, Se, Microe} = erlang:timestamp(),
    {Megase-Megass, Se-Ss, Microe-Micros, S}.

doseive(L, Index) -&gt;
    Isq = Index*Index-1,
    if Isq &gt; length(L) -&gt; [X || X &lt;- L, X /= -1]; %done crossing out
    true -&gt; 
        case  lists:nth(Index, L) == -1 of
        true -&gt; doseive(L, Index + 1); %nothing to cross this pass
        false -&gt; 
            {L1, L2} = lists:split(Isq, L),
             L3 = lists:map(fun(X) -&gt; if X == -1 orelse (X rem Index == 0 andalso X /= Index) -&gt; -1; true  -&gt; X  end end , L2),
             doseive(lists:append(L1, L3), Index + 1)
    end end.


This takes 52 seconds to generate the first two million primes:

6&gt; seive:seive(2000000).
{0,19,53218,
 [1,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,
  73,79,83,89|...]}


I was expecting it to be faster based on other solutions on the web. 

Sticking to serial (I have not even attempted a parallel solution yet, so I'd like to try that on my own first), what are the problems with my code? I looked for "in place" versions of map so that I don't continuously copy lists into new lists, which I think is what is killing me, but the essence of functional is this immutable-ness. 



If I was in an imperative language, I would iterate over a hashmap, but there is no "map-update" function for hashmaps. I guess I could try accessing values in a loop, but this solution better lends itself to imperative languages. Would be nice to have something like

mapupdate(F, V)
%updates all values for keys to V where F(key) is true


I also tried a solution with filter:

doseivev2(L, Index) -&gt;
if Index &gt; length(L) -&gt; L;
true -&gt;
    case Index &gt; length(L) of 
        true -&gt; L;
        false -&gt;
            %if you do filter, you dont know what index p^2 is anymore...
            doseivev2(lists:filter(fun(X) -&gt; X =&lt; Index orelse X rem Index /= 0 end, L), Index + 1)
end end.


but it is WAAAAY slower. Does not even finish for 1M.
You point it, this program copies and traverse the lists too many times. You should think to reduce the size of the list at each prime iteration, you can initialize the first list without all the multiples of 2,3,5 (it is quite easy), you should pass length(L) as a parameter (it needs to traverse the list at each iteration).

Since the sieve algorithm is based on the modification of a set of data, the list is not the best data structure to work with. I think you should have much better result with ets.

[edit] I have tested your version on my laptop using timer:tc/3 and found 24s (your measure is 19.5s, not 52s). a version using ets and the different optimizations I suggest takes 1.2s for the same job.

With 10000000 the times are 252s and 7s, which suggests that with your algorithm the execution time is increasing more than with ets (ration 10 and 6 for a data set 5 time bigger).

Last point, you are returning 1 as a prime which is not correct.