[erlang-questions] generating primes

[Jérôme Desquilbet]

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() ->
   receive
     {prime_msg, P} -> io:format("~p is prime!~n", [P]),
     message_logger()
   end.

prime_collector() ->
   receive
     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) ->
   receive
     Odd ->
       if
         Odd rem Current_Prime == 0 ->
           wait_for_next_prime(Current_Prime);
         true ->
           Odd
       end
   end.

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

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