# beginner needs help with sieve program

Doug Bagley doug@REDACTED
Mon Sep 4 04:50:28 CEST 2000

```Maurice Castro <maurice@REDACTED> writes:
> The Erastoshenes prime number sieve is an excelent starting problem for
> Erlang ... in fact I set it as an exercise in my book. A sample solution
> is provided.
>
> 	http://www.serc.rmit.edu.au/~maurice/erlbk/
> 	http://www.serc.rmit.edu.au/~maurice/erlbk/eg/choice/erasto.erl

Thanks for the hint ... I had made a stupid error, of course!
Here's the fixed version, but yours is still almost 3 times faster
than mine.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-module(sieve).
-export([main/1]).
-import(io, [fwrite/2]).
-import(lists, [seq/2, filter/2]).
-import(math, [sqrt/1]).

%% get the program argument, which is how many test iterations
%% to run
main(Args) ->
[Tmp] = Args,
Iter = list_to_integer(atom_to_list(Tmp)),
test(Iter),
halt(0).

test(N) ->
Primes = sieve(8192),
Count = length(Primes),
case N > 1 of
true  -> test(N-1);
false -> fwrite("Count: ~w\n", [Count])
end.

sieve(Size) ->
sieve(2, sqrt(Size), seq(2,Size)).

sieve(Start, End, Seq) ->
case Start > End of
true ->  Seq;
false -> sieve(Start + 1, End, remove_multiples(Start, Start+Start, Seq))
end.

%% remove multiples of Num from a list without using modulus

% if Head of list is less than the Next multiple we seek
% simply recurse on Tail
remove_multiples(Num, Next, [H|T]) when H < Next ->
[H | remove_multiples(Num, Next, T)];

% this is the rule that actually removes a multiple
% when Head of List matches Next multiple we seek.
remove_multiples(Num, Next, [H|T]) when H == Next ->
remove_multiples(Num, Next+Num, T);

% when we find that the Head is greater than the Next multiple
% we seek, it's time to increment Next by Num
remove_multiples(Num, Next, List) when hd(List) > Next ->
remove_multiples(Num, Next+Num, List);

% end of list
remove_multiples(_, _, []) -> [].
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Cheers,
Doug

```