beginner needs help with sieve program

[Doug Bagley]

Hi, I just started learning about erlang a couple days ago.  The first
thing I wanted to do was to see how efficiently I could program a
sieve of eratosthenes for numbers 2 to 8192.  

Basically I need help finding the bug in the first attempt and I'd
also be interested if anyone has suggestions on how to write a speedy
sieve.


The following is my first attempt, which has runtimes that compare
favorably with Perl, Tcl, Python and Guile, but it has a bug in it:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sieve.erl
% I run it like this:
% > erl -compile sieve ; erl -noinput -s sieve main 100
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

-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).

%% run the test N times
test(N) ->
    Primes = sieve(8192),
    %% there is a bug in our sieve which lets says 2197 is prime
    %% but it is not, it is a multiple of 13
    %% all the other 1028 primes in the list are okay though
    %% so i fudge the correct answer for now
    Count = length(Primes) - 1,
    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 
%% I've rewritten this 2 different ways using case
%% and I get the same results
remove_multiples(Num, Next, [H|T]) when H < Next ->
    [H | remove_multiples(Num, Next, T)];
remove_multiples(Num, Next, [H|T]) when H == Next ->
    remove_multiples(Num, Next+Num, T);
remove_multiples(Num, Next, [H|T]) when H > Next ->
    [H | remove_multiples(Num, Next+Num, T)];
remove_multiples(X, Y, []) -> [].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The next attempt was to use modulus and write it in a very short,
hopefully, erlang way.  This produces correct results, but is
incredibly slow.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sieve.erl
% I run it like this:
% > erl -compile sieve ; erl -noinput -s sieve main 100
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

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

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) -> sievel(seq(2,Size)).

sievel([H|T]) -> [H | sievel(filter(fun(N) -> N rem H > 0 end, T))];
sievel([]) -> [].

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%