読者です 読者をやめる 読者になる 読者になる

Keep on moving

あんまりまとまってないことを書きますよ

エラトステネスの篩を書いてみた。

Erlang Algorithm

勉強の一環として久しぶりにエラトステネスのふるいで素数を求めるコードを書いてみた。久々すぎて理論を忘れておりました><。

エラトステネスの篩 - Wikipedia

-module(erat).

-export([primes/1]).

primes(N) ->
    sieve(lists:seq(2,N)).

sieve(Nums) ->
    LastNum = lists:last(Nums),
    [Num|_Other] = Nums,
    case Num*Num < LastNum of
	true ->
	     [Num|sieve(lists:filter(fun(X) -> X rem Num /= 0 end,_Other))];
	false ->
	    Nums
    end.

実行例

39> erat:primes(100).
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,
 79,83,89,97]

本当はwhenガードが使いたいのだけど、when内ではlists:lastが使えないからできませんでした。
パターンマッチでリスト末尾を取得する方法があればなー。