10

この記事には次のように書かれています。

すべての素数は、 、 、 、または一部の として表す 30k±1こと30k±7が30k±11でき 30k±13ますk。つまり、30 個の数値ごとに 8 ビットを使用して、すべての素数を格納できます。100 万個の素数を 33,334 バイトに圧縮できます

「つまり、すべての素数を格納するために、30 個の数値ごとに 8 ビットを使用できるということです」

この「30個の数字あたり8ビット」はkの場合ですよね？しかし、各k値は必ずしも 1 ビットだけを占めるわけではありません。代わりに8 つの k 値であるべきではありませんか?

「100 万個の素数を 33,334 バイトに圧縮できます」

これがどのように真実なのかわかりません。

次の 2 つのことを示す必要があります。

  • k の値 (任意に大きくすることができます)

  • 8 つの州のうちの 1 つの STATE(-13,-11,-7,-1,1,7,11,13)

「33,334 バイト」がどのように に到達したかについては詳しく説明していませんが、1 つ言えることは、素数がどんどん値が大きくなるにつれて、kの値を格納するためにより多くのスペースが必要になるということです。

では、「33,334 バイト」に修正するにはどうすればよいでしょうか。

4

4 に答える 4

16

この記事は少し誤解を招きます: 100 万個の素数を格納することはできませんが、100 万未満の素数はすべて格納できます。

k の値は、リスト内の位置から取得されます。これらの 8 つの順列 (-13、-11..、11、13) のそれぞれに 1 ビットしか必要ありません。

つまり、k=0 の格納には 8 ビットを使用し、k=1 の格納には 8 ビットを使用し、k=2 の格納には 8 ビットを使用します。 8 ビットごとに k の値 - これは単純に前の 8 ビット + 1 の値です。

1,000,000 / 30 = 33,333 1/3 であるため、30k-13 が 100 万の限界を超えずに k が持つことができるすべての値をカバーするため、100 万未満のどの値が素数であるかを表すために、これらの 8 ビット シーケンスの 33,334 を格納できます。

于 2010-04-10T16:59:22.533 に答える
11

k の各値を保存する必要はありません。100 万未満の素数を格納する場合は、33,334 バイトを使用します。最初のバイトは k=0 に対応し、2 番目のバイトは k=1 に対応します。次に、各バイトで 1 ビットを使用して「素数」または「合成」を示します。 " 30k+1、30k+7 など。

于 2010-04-10T16:57:11.167 に答える
4

これはビットマスクです。素数である可能性のある 30 個の値のうち 8 個の値のそれぞれに 1 ビット、つまり 30 個の数値あたり 8 ビットです。したがって、10^6 までのすべての素数を集計するには、8*10^6/30 = 2666667 ビット = 33334 バイトが必要です。

これが良い方法である理由を説明するには、明白な代替案を検討する必要があります。

もっと素朴な方法は、ビットマスクを使用することです。100 万ビット、125000 バイトが必要です。

素数自体の値を保存することもできます。1000000 まで、値は 20 ビットに収まり、78498 個の素数があるため、1569960 ビット (196245 バイト) という残念な結果になります。

もう 1 つの方法は (素数の検索にはあまり役に立ちませんが)、各素数と次の素数の差を保存することです。100 万未満の場合、これは 6 ビットに収まります (その時点で素数がすべて奇数であることを覚えている限り、偶数の差を格納するだけでよく、したがって最下位ビットを捨てることができます)、470998 ビット == 58874 バイトの場合. (ジャンプしなければならなかったmod-30スロットの数を数えることで、さらに少し削ることができます.)

さて、30 = 2*3*5 以外に 30 について特に特別なことは何もないので、このルックアップは実際に、開始直後にエラトスタネスのふるいパターンのビットマスク表現をたどっています。代わりに 2*3*5*7 = 210 を使用できますが、+- 1、11、13、17、19、23、29、31、37、41、43、47、53、 59、61、67、71、73、79、83、89、97、101、103、48 個の値。30 の 7 ブロックでこれを行っていた場合、7*8=56 ビットが必要になるため、これはわずかな改善ですが、面倒なことはほとんどありません。

したがって、これはかなり小さい素数をコンパクトに格納するための優れたトリックの 1 つです。

(PS 素数がランダムに出現した場合 (ただし、実際に出現するのと同じ数が 1000000 まで出現した場合)、1 から 10^6 までの数の素数に格納される情報量は、1 数あたり ~0.397 ビットになることに注意してください。単純な情報理論の仮定の下では、最初の 100 万個の素数を格納するためにできる最善の方法は、1000000*0.397 ビット、つまり 49609 バイトを使用することだと思うでしょう)。

于 2010-04-11T16:46:59.693 に答える