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

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

エラトステネスの篩 - 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が使えないからできませんでした。
パターンマッチでリスト末尾を取得する方法があればなー。