0 Replies - 1240 Views - Last Post: 19 December 2010 - 02:11 PM

#1 macosxnerd101  Icon User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12211
  • View blog
  • Posts: 45,290
  • Joined: 27-December 08

[Erlang] Sieve of Eratosthenes

Posted 19 December 2010 - 02:11 PM

Description: Invoke primes:sieve(numPrimes) to generate a list of primes from 2-numPrimes.Generates a list of primes from 2-n.
-module(primes).
-export([sieve/1]).

%The function to initiate the sieveing
%It starts by building the list of numbers from
%2-N, excluding evens after 2
%The from 3-N is then pruned to remove composites
%Afterwords, the list is reassembled and returned
sieve(N) ->

    %As lists are recursively defined in Erlang
    %It is broken apart into the first elem Head
    %and the rest of the list Tail.
    %The original list is in tact and two new variables
    %Head and Tail are created
    [Head | Tail] = build_list(N),

    %Prune the rest of the list, then reassemble it with 2
    [Head] ++ prune(Tail).

%If the user wants to generate primes from 2 through a number < 2
%An empty list is returned
build_list(N) when (N < 2) -> [];

%Evens other than two are ignored
build_list(N) when ((N /= 2) and (N rem 2 == 0)) -> build_list(N-1) ++ [];

%Otherwise, the list is built from the back forwards
build_list(N) when N > 1 -> build_list(N-1) ++ [N].

%If no elements in the list remain, then return an empty list
prune(List) when length(List) == 0 -> [];

%otherwise
prune(List) when length(List) > 0 -> 

   %pull the first element from the list
   [Head | Tail] = List,

   %and remove all elements evenly divisible by it
   %and reassemble the list with the pulled element
   [Head] ++ prune(remove(Head, Tail)).


remove(Head, Tail) -> 
    if 
	 length(Tail) == 0 -> [];
         length(Tail) > 0 ->
		    [H | T] = Tail,
			if
				(H rem Head == 0) -> remove(Head, T);
				(H rem Head /= 0) -> [H] ++ remove(Head, T)
			end
	end.


Is This A Good Question/Topic? 0
  • +

Page 1 of 1