7

まず第一に、私はこのフォーラムで多くのことをチェックしましたが、十分に速いものを見つけられませんでした。指定された範囲の素数を返す関数を作成しようとしています。たとえば、エラトステネスの篩を使用してこの関数を (C# で) 実行しました。Atkin のふるいも試しましたが、Eratosthenes の方が高速に実行されます (私の実装では):

public static void SetPrimesSieve(int Range)
    {
        Primes = new List<uint>();
        Primes.Add(2);
        int Half = (Range - 1) >> 1;
        BitArray Nums = new BitArray(Half, false);
        int Sqrt = (int)Math.Sqrt(Range);
        for (int i = 3, j; i <= Sqrt; )
        {
            for (j = ((i * i) >> 1) - 1; j < Half; j += i)
                Nums[j] = true;
            do
                i += 2;
            while (i <= Sqrt && Nums[(i >> 1) - 1]);
        }
        for (int i = 0; i < Half; ++i)
           if (!Nums[i])
                Primes.Add((uint)(i << 1) + 3);
    }

私が見つけたコードとアルゴリズムよりも約 2 倍高速に実行されます...素数を見つけるためのより高速な方法があるはずです。

4

5 に答える 5

9

このトピックに関するアルゴリズムを検索するとき（プロジェクトオイラーの場合）、もっと速く何かを見つけたのを覚えていません。速度が本当に問題になる場合は、素数を保存するだけで、それを調べるだけでよいと考えたことはありますか？

編集：グーグル検索でこれが見つかりました。最速の方法は、結果をページングして必要に応じて検索することです。

もう1つの編集-ここでより多くの情報を見つけることができます。本質的にはこのトピックの複製です。そこのトップの投稿は、アトキンのふるいは、その場で生成する限り、時代よりも速かったと述べています。

于 2010-09-27T21:57:22.330 に答える
2

これまでの私の経験で最速のアルゴリズムは、2、3、および 5 のホイール因数分解を使用したエラトステネスのふるいであり、残りの数の素数はバイト配列のビットとして表されます。私の 3 年前のラップトップの 1 つのコアの Java では、10 億までの素数を計算するのに 23 秒かかります。

wheel factorization を使用すると、Atkin のふるいは約 2 倍遅くなりましたが、通常のふるいでBitSetは約 30% 速くなりました。

この回答も参照してください。

于 2010-10-28T12:39:00.563 に答える
1

C で書かれた I 350M-notebook で 0.65 秒間 2 ～ 90 000 000 の範囲の素数を見つけることができるアルゴリズムを作成しました。必要な具体的なビットのインデックス。たとえば、2 番目のフォールドが必要な場合、具体的なビットはたとえば ....10101000 ... 左から読み取ると ... インデックス 4,6,8 が得られます ... 以上です

于 2011-03-22T09:50:21.560 に答える
0

いくつかのコメント。

  1. 速度を上げるには、事前計算してからディスクからロードします。超高速です。私はずっと前にJavaでそれをしました。

  2. 配列として保存せず、奇数のビットシーケンスとして保存します。メモリ効率が大幅に向上

  3. 速度の問題が、この特定の計算を高速に実行することである場合 (事前計算してディスクからロードできない理由を正当化する必要があります)、より優れた Atkin のふるいをコーディングする必要があります。より高速です。でもほんの少し。

  4. これらの素数の最終用途を示していません。あなたが申請書を私たちに伝えていないので、私たちは何かを完全に見逃しているかもしれません. アプリケーションのスケッチを教えてください。答えは、あなたのコンテキストにより適したものになります。

  5. いったいなぜ、もっと速いものが存在すると思いますか? あなたは自分の予感を正当化していません。これは非常に難しい問題です。（つまり、何かをより速く見つけることです）

于 2010-09-28T03:39:23.283 に答える
0

Sieve of Atkinを使用すると、それよりもうまく処理できますが、迅速かつ正確に実装するのは非常に困難です。ウィキペディアの疑似コードを単純に翻訳しただけでは、おそらく十分ではありません。

于 2010-09-28T12:06:54.590 に答える