0

我已经编辑了程序，以便它可以工作（使用小数字）但是我不明白如何按照建议实现累加器。原因是因为P在整个过程中都在变化，所以我不知道我应该以哪个粒度来分解母列表。Erastosthenes 的筛子只对生成较小的素数有效，所以也许我应该选择一个不同的算法来使用。有人可以推荐一个体面的算法来计算 600851475143 的最高素数吗？请不要给我代码我更喜欢这种性质的维基百科文章。

    -module(sieve).
    -export([find/2,mark/2,primes/1]).

    primes(N) -> [2|lists:reverse(primes(lists:seq(2,N),2,[]))].

    primes(_,bound_reached,[_|T]) -> T;
    primes(L,P,Primes) -> NewList = mark(L,P),
        NewP = find(NewList,P),
        primes(NewList,NewP,[NewP|Primes]).

    find([],_) -> bound_reached;
    find([H|_],P) when H > P -> H;
    find([_|T],P) -> find(T,P). 


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

    mark([],_,_,NewList) -> NewList;
    mark([_|T],P,Counter,NewList) when Counter rem P =:= 0 -> mark(T,P,Counter+1,[P|NewList]);
    mark([H|T],P,Counter,NewList) -> mark(T,P,Counter+1,[H|NewList]).

我发现写这个非常困难，而且我知道它有一些不是很优雅的东西，比如我将 2 硬编码为质数的方式。因此，我将不胜感激任何 C&C 以及有关如何解决此类问题的建议。我查看了其他实现，我完全不知道作者如何以这种方式思考，但它是我想掌握的东西。

我已经弄清楚我可以忘记这个列表，直到找到最近的素数，但是我不知道我应该如何产生一个结束界限（微妙的幽默）。我认为可能有一些我可以使用的东西，比如 lists:seq(P,something) 并且当我使用模数而不是每次都将其重置为 0 时，计数器将能够处理它。我只做过AS级别的数学，所以我不知道这是什么。

我什至不能这样做，我可以吗？因为我将不得不从整个列表中删除 2 的倍数。我认为除非我将数据缓存到硬盘驱动器，否则该算法将不起作用，所以我重新寻找更好的算法。

我现在正在考虑编写一个算法，它只使用一个计数器并保留一个素数列表，这些素数是不与先前生成的素数均分的数字，这是一个好方法吗？

这是我写的新算法，我认为它应该可以工作，但我收到以下错误“sieve2.erl:7: call to local/imported function is_prime/2 is legal in guard”我认为这只是 erlang 的一个方面我不明白。但是，我不知道如何找到有关它的材料。[我故意不使用高阶函数等，因为我只在 learnyousomeerlang.org 中阅读了关于递归的部分内容]

    -module(sieve2).
    -export([primes/1]).

    primes(N) -> primes(2,N,[2]).

    primes(Counter,Max,Primes) when Counter =:= Max -> Primes;
    primes(Counter,Max,Primes) when is_prime(Counter,Primes) -> primes(Counter+1,Max,[Counter|Primes]);
    primes(Counter,Max,Primes) -> primes(Counter+1,Max,Primes).

    is_prime(X, []) -> true;
    is_prime(X,[H|T]) when X rem H =:= 0 -> false;
    is_prime(X,[H|T]) -> prime(X,T).

第二个算法不会崩溃但运行得太慢，我想我应该重新实现第一个但这次忘记了直到最近发现的素数的数字，有人知道我可以用什么作为结束界限吗？在查看其他解决方案之后，似乎人们有时只是设置了一个任意限制，即 200 万（这是我真的不想做的事情。其他人使用“懒惰”的实现，这就是我认为我正在做的事情。

4

3 回答 3

4

这个：

lists:seq(2,N div 2)

分配一个列表，正如效率指南所说，一个列表每个元素至少需要两个字的内存。（一个字是 4 字节还是 8 字节，取决于你是 32 位还是 64 位 Erlang 虚拟机。）所以如果N是 600851475143，如果我计算正确的话，这将需要 48 TB 的内存。（与 Haskell 不同，Erlang 不进行惰性求值。）

所以你需要使用累加器来实现它，类似于你Counter在mark函数中所做的。对于递归函数的停止条件，您不会检查列表是否为空，而是检查累加器是否达到最大值。

于 2013-02-26T14:57:35.620 回答
1

顺便说一句，您不需要测试所有数字到 N/2。测试到 sqrt(N) 就足够了。

这里我写了一个版本，需要 20 秒才能在我的机器上找到答案。它使用一种惰性素数列表并通过它们折叠。这很有趣，因为我很久以前就使用 Haskell 解决了一些项目欧拉问题，而在 Erlang 上使用相同的方法有点奇怪。

于 2013-02-26T18:45:16.337 回答
0

在您的更新3：

primes(Counter,Max,Primes) when Counter =:= Max -> Primes;
primes(Counter,Max,Primes) when is_prime(Counter,Primes) -> primes(Counter+1,Max,[Counter|Primes]);
primes(Counter,Max,Primes) -> primes(Counter+1,Max,Primes).

您不能像在 Haskell 中那样使用自己定义的函数作为保护子句。您必须重写它才能在 case 语句中使用它：

primes(Counter,Max,Primes) when Counter =:= Max ->
    Primes;
primes(Counter,Max,Primes) ->
    case is_prime(Counter,Primes) of
        true ->
            primes(Counter+1,Max,[Counter|Primes]);
        _ ->
            primes(Counter+1,Max,Primes)
    end.
于 2013-02-28T08:14:29.343 回答