マルチスレッドで素数の計算

Erlang 30分プログラム

30分プログラム、その159。ひろ氏がお昼ご飯のときに、「マルチスレッドで素数の計算がしたい」というようなことを言っていたので、Erlangでやってみる。

方法はフェルマーテスト(id:mzp:20071001:fermat)。あるスレッドが、ほかのスレッドの計算結果に影響を受けないから、マルチスレッド向きかな、と勝手に判断。

使い方

1> c("prime.erl").

% 2から10までの素数を求める
2> prime:start(10).
2
3
5
7
true

% 2から100までの素数を求める
3> prime:start(100).
2
3
5
7
11
13
15
...
...

んー、なんか結果が間違ってる気がする。15は素数じゃないし。

ソースコード

-module(prime).
-export([start/1]).

% math:powは誤差が生じるし浮動小数なので、
% 整数版を定義する。
pow(_,0)-> 1;
pow(X,1)-> X;
pow(X,N) -> case N rem 2 of
		0 -> pow(X*X,N div 2);
		1 -> X*pow(X*X,N div 2)
	    end.

gcd(M,0) -> M;
gcd(M,N) -> gcd(N,M rem N).

% フェルマーテスト    
fermat(N,A)-> case gcd(N,A) of
		  1 -> 
		      pow(A,N-1) rem N =/= 1;
		  _ ->
		      false
	      end.

% N回のフェルマーテストを実行する
fermat_test(From,N,0) ->
    From ! {prime,N};
fermat_test(From,N,Times) ->
    A = random:uniform(1000)+2,
    case fermat(N,A) of
	true ->
	    From ! {not_prime,0};
	false ->
	    fermat_test(From,N,Times-1)
    end.

% 結果を待つ
wait(0) -> true;
wait(M) ->
    receive
	{prime,N} -> io:format("~p~n",[N]),
		     wait(M-1);
	_ -> wait(M-1)
    end.

start(To) ->
    S = self(),
    lists:map(fun(N)-> spawn(fun()-> fermat_test(S,N,10) end) end,lists:seq(2,To)),
    wait(To-1).

参考