0

プログラムを編集して（少数で）動作するようにしましたが、提案されているアキュムレータを実装する方法がわかりません。その理由は、プロセス全体で P が変化するためです。そのため、マザー リストをどの粒度で分割すればよいかわかりません。エラストステネスのふるいは、より小さな素数を生成する場合にのみ効率的であるため、使用する別のアルゴリズムを選択する必要があったかもしれません。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 illegal in guard」理解できません。しかし、それについて読むための資料をどのように見つけることができるかわかりません。[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).

2 番目のアルゴリズムはクラッシュしませんが、実行が遅すぎます。最初のアルゴリズムを再実装する必要があると考えていますが、今回は、最近発見された素数までの数値を忘れています。エンド バウンドとして使用できるものを誰か知っていますか? 他のソリューションを見た後、人々は時々恣意的な制限、つまり200万を設定しているようです（これは私が本当にやりたくないことです。他の人は「怠惰な」実装を使用しました。これは私がやっていると思います.

4

3 に答える 3

4

これ：

lists:seq(2,N div 2)

リストを割り当てます。効率ガイドにあるように、リストには要素ごとに少なくとも 2 ワードのメモリが必要です。(Erlang 仮想マシンが 32 ビットか 64 ビットかに応じて、1 ワードは 4 バイトまたは 8 バイトです。) したがって、Nが 600851475143 の場合、正しく数えると 48 テラバイトのメモリが必要になります。(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

update3 で:

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 に答える