# [erlang-questions] generating primes

Jérôme Desquilbet jerome@REDACTED
Wed Oct 15 08:05:47 CEST 2008

```Imre Palik a écrit :
> Hi,
>
> I am playing with Project Euler nowdays, and in the last few problems
> I solved I had problems generating primes fast enough.  Currently I
> am using the following implementation of the Sieve of Eratosthenes:
>
> sieve([]) -> []; sieve([H|T]) -> [H|sieve([X||X<-T,X rem H =/= 0])].
>
> ...

Would you like a suboptimal algorithm?
Here it is: N primes --> N sieves --> N erlang processes.
It's all about playing after all... :-)
Jérôme.
PS: it's translated from an Ada example from Alan Burns and Andy Wellings.

-----8<--------------------------

-module(eratosthenes).
-export([message_logger/0, run/0, prime_collector/0,
process_next_numbers/2, start_sieve/2, wait_for_next_prime/1]).

message_logger() ->
{prime_msg, P} -> io:format("~p is prime!~n", [P]),
message_logger()
end.

prime_collector() ->
Prime ->
logger ! {prime_msg, Prime},
prime_collector()
end.

run() ->
register(logger, spawn(?MODULE, message_logger, [])),
Collector = spawn(?MODULE, prime_collector, []),
Collector ! 1,
Collector ! 2,
First_Sieve = spawn(?MODULE, start_sieve, [3, Collector]),
give_odd(5, First_Sieve).

give_odd(Odd, First_Sieve) ->
First_Sieve ! Odd,
give_odd(Odd+2, First_Sieve).

start_sieve(Prime, Collector) ->
Collector ! Prime,
Next_Prime = wait_for_next_prime(Prime),
Next_Sieve = spawn(?MODULE, start_sieve, [Next_Prime, Collector]),
process_next_numbers(Prime, Next_Sieve).

wait_for_next_prime(Current_Prime) ->
Odd ->
if
Odd rem Current_Prime == 0 ->
wait_for_next_prime(Current_Prime);
true ->
Odd
end
end.

process_next_numbers(Current_Prime, Next_Sieve) ->
Odd ->
if
Odd rem Current_Prime /= 0 ->
Next_Sieve ! Odd;
true ->
false
end,
process_next_numbers(Current_Prime, Next_Sieve)
end.

-----8<--------------------------

```