# R – Sieve of Eratosthenes in Erlang

erlangsieve-of-eratosthenes

I'm in the process of learning Erlang. As an exercise I picked up the Sieve of Eratosthenes algorithm of generating prime numbers. Here is my code:

``````-module(seed2).
-export([get/1]).

get(N) -> WorkList = lists:duplicate(N, empty),
get(2, N, WorkList, []).

get(thats_the_end, _N, _WorkList, ResultList) -> lists:reverse(ResultList);
get(CurrentPrime, N, WorkList, ResultList) -> ModWorkList = markAsPrime(CurrentPrime, N, WorkList),
NextPrime = findNextPrime(CurrentPrime + 1, N, WorkList),
get(NextPrime, N, ModWorkList, [CurrentPrime|ResultList]).

markAsPrime(CurrentPrime, N, WorkList) when CurrentPrime =< N -> WorkListMod = replace(CurrentPrime, WorkList, prime),
markAllMultiples(CurrentPrime, N, 2*CurrentPrime, WorkListMod).

markAllMultiples(_ThePrime, N, TheCurentMark, WorkList) when TheCurentMark > N -> WorkList;
markAllMultiples(ThePrime, N, TheCurrentMark, WorkList) -> WorkListMod = replace(TheCurrentMark, WorkList, marked),
markAllMultiples(ThePrime, N, TheCurrentMark + ThePrime, WorkListMod).

findNextPrime(Iterator, N, _WorkList) when Iterator > N -> thats_the_end;
findNextPrime(Iterator, N, WorkList) -> I = lists:nth(Iterator, WorkList),
if
I =:= empty -> Iterator;
true -> findNextPrime(Iterator + 1, N, WorkList)
end.

replace(N, L, New)-> {L1, [_H|L2]} = lists:split(N - 1, L),
lists:append(L1, [New|L2]).
``````

This code actually works ðŸ™‚ . The problem is that I have this feeling that it is not the best possible implementation.

My question is what would be the "erlangish" way of implementing the "Sieve of Eratosthenes"

EDIT: OK, Andreas solution is very good but it is slow. Any ideas how to improve that?

#### Best Solution

Here's a simple (but not terribly fast) sieve implementation:

``````-module(primes).
-export([sieve/1]).
-include_lib("eunit/include/eunit.hrl").

sieve([]) ->
[];
sieve([H|T]) ->
List = lists:filter(fun(N) -> N rem H /= 0 end, T),
[H|sieve(List)];
sieve(N) ->
sieve(lists:seq(2,N)).
``````