beginner needs help with sieve program

Doug Bagley <>
Mon Sep 4 04:50:28 CEST 2000


Maurice Castro <> 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



More information about the erlang-questions mailing list