Sieve of Eratosthenes Redux PDF Print E-mail
Thursday, 09 April 2009 13:56

So I was a little disappointed by my last effort, it just wasn't elegant enough.  I'm probably going to venture to list comprehensions, but haven't gone there yet.  I have a cleaned up version of the last one, it is nicer, and makes more sense(and fixes a bug- 5 points for you if you can find it).

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

Book Wish List

StackOverflow