Erlang中Eratosthenes的筛子
Erlang中Eratosthenes的筛子
提问于 2008-09-28 20:08:31
我正在学习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]).这段代码实际上是有效的:)。问题是，我有一种感觉，那不是最好的实现。
我的问题是，实现“埃拉托色尼筛子”的"erlangish“方法是什么？
编辑:好的，Andreas解决方案很好，但它很慢。有什么想法可以改善这一点吗？
回答 8
Stack Overflow用户
回答已采纳
发布于 2008-10-05 20:35:10
下面是一个简单(但不是非常快)的sieve实现：
-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)).Stack Overflow用户
发布于 2009-03-01 00:42:17
这是我的sieve实现，它使用列表理解并尝试尾递归。我颠倒了末尾的列表，这样质数就可以排序了：
primes(Prime, Max, Primes,Integers) when Prime > Max ->
lists:reverse([Prime|Primes]) ++ Integers;
primes(Prime, Max, Primes, Integers) ->
[NewPrime|NewIntegers] = [ X || X <- Integers, X rem Prime =/= 0 ],
primes(NewPrime, Max, [Prime|Primes], NewIntegers).
primes(N) ->
primes(2, round(math:sqrt(N)), [], lists:seq(3,N,2)). % skip odds在我的2 2ghz上，大约需要2.8毫秒才能计算出高达2百万的素数。
Stack Overflow用户
发布于 2008-09-28 20:14:23
我通过使用并发处理来解决这个问题。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/146622
复制相关文章
相似问题