Sieve of Eratosthenes in Erlang

April 9, 2009 8:18 p.m.

This is my first real attempt at a semi-useful program in Erlang. It is the Sieve of Eratosthenes, which is a prime number generator. The main function is primes() which accepts the number that you would like to count up to. Luckly, Erlang is a Functional language, so I was able to do some fun things.

I had to modify the algorithm, as the original algorithm uses arrays, and arrays aren’t really used in Erlang. I suppose this is probably due to the functional roots that Erlang has. Scheme in practice tends to stay away from vectors and uses lists more. I decided to use lists in Erlang, and was able to do some nice recursion, as is normal with Scheme.

-module(sieve).
-export([primes/1]).

%% Removes the multiples of a number from a list
remove_multiples(_, []) -> [];
remove_multiples(N, [H|T]) when (H rem N == 0) ->
        remove_multiples(N, T);
remove_multiples(N, [H|T]) ->
        [H|remove_multiples(N, T)].

%% Generate primes by creating a list of numbers from 0 to N.
%% Then recurse through the list, eliminating multiples off the tail at each recursion.
primes(N) ->
        primes(lists:seq(2,N), math:sqrt(N)).
primes([H|T], StopNumber) when H =
        [H|primes(remove_multiples(H, T), StopNumber)]; %% Does this blow your mind?
primes(L,_)-> L.

I’m not experienced with Erlang yet, so my apologies if I have bad Erlang style.

comments powered by Disqus