素数計算 - みずぴー日記

30分プログラム、その274。Erlangで素数計算。
Project EulerのProblem12を解くために素因数分解がいるので、それの準備。
素数のリストが欲しいけれど、ムダな計算は避けたい。Schemeとかだったら遅延リストやストリームを使うタイミングだけど、Erlangだったら、別プロセスで準備するのが普通だろう、と思ったので素数を計算するサーバを作ってみた。

使い方

% 素数サーバ起動
1> prime_srv:start().
true

% 10までの素数を取得
2> prime_srv:get(10).
additional prime:[3,4,5,6,7,8,9,10] 
[3,
 5,
 7,
 9,
 2]

% 10までの素数を再取得。再計算はしない
3> prime_srv:get(10).
[3,
 5,
 7,
 9,
 2]

ソースコード

-module(prime_srv).
-compile(export_all).

loop(Checked,Prime) -> 
    receive
	{From,N} ->
	    if
		N =< Checked -> 
		    From ! { self(), lists:filter(fun (I)-> I =< N end ,Prime) },
		    loop(Checked,Prime);
		true -> 
		    Int = lists:seq(Checked+1,N),
		    io:format("additional prime:~p ~n",[Int]),
		    Prime2 = lists:foldl(fun(X,L)-> 
						 lists:filter(fun(Y)-> Y rem X =/= 0 end,L)
					 end,
					 Int,
					 Prime),
		    Prime3 = Prime2 ++ Prime,
		    From ! { self(),Prime3},
		    loop(N,Prime3)
	    end
    end.

get(N) -> 
    prime_srv ! { self(),N },
    receive
	{ _ , L } -> L
    end.

start() ->
    register(prime_srv,spawn(fun ()-> loop(2,[2]) end)).

参考

過去の30分プログラム