# [erlang-questions] Generating Primes and the O'Neill paper

Angel Alvarez <>
Thu Dec 17 00:03:52 CET 2009

```Opps !!  15 is not prime is'nt it?

Ive include an improved version...

compare(X,Y) ->
case X == Y of
true ->
equal;
false ->
case X > Y of
true ->
greater;
false ->
smaller
end
end.

is there a better way of writing this test?

/Angel

El Miércoles, 16 de Diciembre de 2009 Angel Alvarez escribió:
> El Miércoles, 16 de Diciembre de 2009 James Aimonetti escribió:
> > I have been working the Project Euler problems and wanted to see what
> > the list thought about my implementation of a prime number generator
> > that is based off the Melissa O'Neill paper[1]. I also used a lazy list
> > idea from one of Joe Armstrong's suggestions[2] concerning a Euler
> > problem. My implementation uses the priority queue (page 7 of the PDF),
> > and I'm using a skew heap I found[3] on this list to accomplish that,
> > which I modified to handle key-value pairs instead of just keys.
> >
> > I made a pastie[4] to view the code.
> >
> > I tried to stay true to the Haskell version in the paper but had to
> > modify some parts. I don't know Haskell so I easily could have lost
> > something in the translation.
> >
> > Oh, the function is called queue because I was playing with other
> > methods, like the unfaithful sieve, but I've only included the queue/1
> > in the pastie. I am going to try the wheel and other optimizations
> > talked about in the paper, but wanted a sanity check from the gurus that
> > my Erlang is decent and the implementation isn't totally bunk.
> >
> >
> > [1] - http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
> > [2] - http://www.erlang.org/cgi-bin/ezmlm-cgi?4:mss:177:khdaceipfabbicmifdhf
> > [3] -
> > http://www.erlang.org/pipermail/erlang-questions/2007-August/028769.html
> > [4] - http://pastie.org/746050
> >
> Hi this paper is very interesting, but being novice icant hardly say you
> something about your code. Maybe you can check mine for a
> multiprocess approach.
>
> Ive include my try on this "genuine" erathostenes sieve.
>
> every worker stores one prime and properly crosses off on the fly when the numbers
> are testet. Its a kind of lazy as it creates new worker in demand...
>
> With my code you can do a naive exercise:
>
> :~/Documents/Personal/Erlang/Code/primality> erlc multi_erathostenes.erl
> :~/Documents/Personal/Erlang/Code/primality> erl
> Erlang R13B01 (erts-5.7.2) [source] [rq:1] [async-threads:0] [hipe] [kernel-poll:false]
>
> Eshell V5.7.2  (abort with ^G)
>
> 1> OnePID=spawn(multi_erathostenes,worker,[2,4]).
> <0.35.0>
> 2> [ OnePID ! {test,X} || X <- [3,4,5,6,7,8,9,10,11]].
>
> [Worker of prime: 2 (4)] Spawn new worker for Prime: 3
> [Worker of prime: 2 (4)] Found composite: 4
> [Worker of prime: 2 (6)] passing along: 5
> [Worker of prime: 2 (6)] Found composite: 6
> [Worker of prime: 3 (9)] Spawn new worker for Prime: 5
> [Worker of prime: 2 (8)] passing along: 7
> [Worker of prime: 2 (8)] Found composite: 8
> [Worker of prime: 3 (9)] passing along: 7
> [Worker of prime: 2 (10)] passing along: 9
> [Worker of prime: 5 (25)] Spawn new worker for Prime: 7
> [Worker of prime: 2 (10)] Found composite: 10
> [Worker of prime: 3 (9)] Found composite: 9
> [Worker of prime: 2 (12)] passing along: 11
> [Worker of prime: 3 (12)] passing along: 11
> [Worker of prime: 5 (25)] passing along: 11
> [Worker of prime: 7 (49)] Spawn new worker for Prime: 11
>
>
> /Angel

--
No imprima este correo si no es necesario. El medio ambiente está en nuestras manos.
->>-----------------------------------------------
Clist UAH a.k.a Angel
---------------------------------[www.uah.es]-<<--

Tú lo compras, yo lo copio. Todo legal.
-------------- next part --------------
% Multi "Genuine" Erathostenes

%         02    03    05    07    11    13    17
% P 02 -> 04
% P 03    04 -> 09
% C 04 == 04    09
% P 05    06    09 -> 25
% C 06 == 06    09    25
% P 07    08    09    25 -> 49
% C 08 == 08    09    25    49
% C 09    10 == 09    25    49
% C 10 == 10    12    25    49
% P 11    12    12    25    49 -> 121
% C 12 == 12    12    25    49    121
% P 13    14    15    25    49    121 -> 169
% C 14 == 14    15    25    49    121    169
% C 15    16 == 15    25    49    121    169
% C 16 == 16    18    25    49    121    169
% P 17    18    18    25    49    121    169 -> 289

-module(multi_erathostenes).
-compile(export_all).

compare(X,Y) ->
case X == Y of
true ->
equal;
false ->
case X > Y of
true ->
greater;
false ->
smaller
end
end.

worker(Prime,UpperBound)->
{test,Number} ->
case compare(Number,UpperBound) of
equal ->
io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
worker(Prime,UpperBound + Prime);
smaller ->
io:format("[Worker of prime: ~w (~w)] Spawn new worker for Prime: ~w~n",[Prime,UpperBound,Number]),
NextPID =spawn(?MODULE,worker,[Number,Number*Number]),
worker(Prime,UpperBound,NextPID)
end
end.

worker(Prime,UpperBound,NextPID) ->
{test,Number} ->
case compare(Number,UpperBound) of
equal ->
io:format("[Worker of prime: ~w (~w)] Found composite: ~w~n",[Prime,UpperBound,Number]),
worker(Prime,UpperBound + Prime,NextPID);
smaller ->
io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
NextPID ! {test,Number},
worker(Prime,UpperBound,NextPID);
greater ->
io:format("[Worker of prime: ~w (~w)] passing along: ~w~n",[Prime,UpperBound,Number]),
NextPID ! {test,Number},
worker(Prime,UpperBound+Prime,NextPID)
end
end.

% main(LimiteSuperior) ->
% FirstWorkerPID = spawn(?MODULE, worker,[2,4]),
% PID_Worker = pool:pspawn(?MODULE, worker,[1,PID_Acumulador,?MAXPRIMES,[] ]),
% T1 = erlang:now(),