erlang - Erlang的Eratosthenes筛

Closed. This question is opinion-based。它当前不接受答案。












想改善这个问题吗？更新问题，以便editing this post用事实和引用来回答。

6年前关闭。



Improve this question





我正在学习Erlang。作为练习，我学习了生成素数的Sieve of Eratosthenes算法。这是我的代码：

-module(seed2).
-export([get/1]).

get(N) -> WorkList = lists:duplicate(N, empty),
          get(2, N, WorkList, []).

get(thats_the_end, _N, _WorkList, ResultList) -> lists:reverse(ResultList);
get(CurrentPrime, N, WorkList, ResultList) -> ModWorkList = markAsPrime(CurrentPrime, N, WorkList),
                                              NextPrime = findNextPrime(CurrentPrime + 1, N, WorkList),
                                              get(NextPrime, N, ModWorkList, [CurrentPrime|ResultList]).


markAsPrime(CurrentPrime, N, WorkList) when CurrentPrime =< N -> WorkListMod = replace(CurrentPrime, WorkList, prime),
                                                                 markAllMultiples(CurrentPrime, N, 2*CurrentPrime, WorkListMod).

markAllMultiples(_ThePrime, N, TheCurentMark, WorkList) when TheCurentMark > N -> WorkList;
markAllMultiples(ThePrime, N, TheCurrentMark, WorkList) -> WorkListMod = replace(TheCurrentMark, WorkList, marked),
                                                           markAllMultiples(ThePrime, N, TheCurrentMark + ThePrime, WorkListMod).

findNextPrime(Iterator, N, _WorkList) when Iterator > N -> thats_the_end;
findNextPrime(Iterator, N, WorkList) -> I = lists:nth(Iterator, WorkList),
                                        if
                                          I =:= empty -> Iterator;
                                          true -> findNextPrime(Iterator + 1, N, WorkList)
                                        end.

replace(N, L, New)-> {L1, [_H|L2]} = lists:split(N - 1, L),
                     lists:append(L1, [New|L2]).

这段代码实际上是有效的：）。问题是我感觉这不是最好的实现。

我的问题是实施“ Eratosthenes筛”的“古怪”方式是什么？

编辑：好的，Andreas解决方案很好，但是很慢。有什么想法可以改善吗？

最佳答案

这是一个简单的（但并非很快）筛子实现：

-module(primes).
-export([sieve/1]).
-include_lib("eunit/include/eunit.hrl").

sieve([]) ->
    [];
sieve([H|T]) ->
    List = lists:filter(fun(N) -> N rem H /= 0 end, T),
    [H|sieve(List)];
sieve(N) ->
    sieve(lists:seq(2,N)).