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
More information about the erlang-questions
mailing list