0

我正在尝试在erlang中实现一个eratosphenes筛子。但是我无法通过算法的第二步。我用 p 填充标记的条目，这样当我遍历列表直到找到大于 p 的值时，我就会知道它也是素数。

    -module(sieve).
    -export([primes/0]).

    primes() -> L = lists:seq(2,20),
    mark(L,2).

    mark(L,P) -> mark(L,P,2,[]).

    mark([],_,_,N) -> N;
    mark([_|T],P,C,N) when C =:= P -> mark(T,P,C+1,[N|[P]]);
    mark([H|T],P,C,N) -> mark(T,P,C,[N|[H]]).

我也尝试过附加一个 ++ ，但这会产生相同的结果。

4

2 回答 2

1

上面的代码只运行一次。

primes() ->
    List = lists:seq(2,100),
    mark([], List).

mark(Primes, []) ->
    lists:reverse(Primes);
mark(Primes, _List = [H| T]) ->
    mark([H | Primes], H, T, []).

mark(Primes, _P, [], NewList) -> 
    mark(Primes, lists:reverse(NewList));
mark(Primes, P, [H | T], NewList) when H rem P == 0 ->
    mark(Primes, P, T, NewList);
mark(Primes, P,[H | T], NewList) ->
    mark(Primes, P, T, [H | NewList]).

即使没有反向也可以工作，但为了保持正确的顺序，我们可以做反向或 ++

于 2013-02-24T16:16:10.940 回答
0

如果您的目的是教育，将素数存储在列表中是可以的，vinod 的解决方案很好。但是如果你必须使用这个列表，那么我认为 ETS 表（有序集）可能更方便。

另一点，erathostene 算法的一个弱点是你首先创建一个巨大的列表（如果你需要很多），然后删除大部分元素。您可以轻松地将初始列表除以 2 L = [2|lists:seq(3,Max,2)]。您还可以在没有 2、3、5 的倍数的情况下初始化列表/表格，创建时间更短，消除时间更短。

于 2015-01-22T19:54:10.413 回答