# [Erlang] Sieve of Eratosthenes

Page 1 of 1

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

### #1 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12211
• 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

%Prune the rest of the list, then reassemble it with 2

%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

%and remove all elements evenly divisible by it
%and reassemble the list with the pulled element

if
length(Tail) == 0 -> [];
length(Tail) > 0 ->
[H | T] = Tail,
if