[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() ->
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<--------------------------
More information about the erlang-questions
mailing list