有效地存儲素數

Question

This article的名單說：

每一個素數可以表示爲 30k±1，30k±7，30k±11，或 30k±13一些k。 這意味着我們可以使用每個 的三位數字來存儲所有的素數;一百萬素數可 壓縮到33,334字節

---

「這意味着我們可以使用每個30號八位來存儲所有的素數」

這種「每八位30號」將爲k，對嗎？但是每個值不一定只佔用一位。不應該是八個k值而不是？

---

「百萬素可以壓縮到33,334字節」

我不知道如何這是真的。

我們需要指出兩點：

• 的k值（可以任意大）

• 從八個州的一個狀態(-13,-11,-7,-1,1,7,11,13)

我不遵循如何「33,334字節」到達，但我可以說一件事：隨着素數越來越大，價值較大，我們將需要更多空間來存儲價值k。

那麼，我們可以將它修復爲「33,334字節」嗎？

Answer 1

您不需要存儲k的每個值。如果要將素數存儲在100萬以下，請使用33,334字節 - 第一個字節對應於k = 0，第二個對應k = 1等。然後，在每個字節中，使用1位來表示「素數」或「合成「對於30k + 1,3k + 7等。

Answer 2

這篇文章有點誤導我們：我們不能存儲100萬個素數，但我們可以存儲100萬以下的所有素數。

k的值來自它在列表中的位置。我們只需要8位置換中的每一位（-13，-11 ...，11,13）

換句話說，我們將使用8位來存儲k = 0,8來存儲k = 1,8，以存儲k = 2等。通過順序地進行這些操作，我們不需要爲每8位指定k的值 - 它僅僅是前8位+1的值。

由於1,000,000/30 = 33,333 1/3，我們可以存儲33,334這8位序列，表示哪些值低於100萬是素數，因爲我們覆蓋了所有k值可以不超過30k-13的值100萬。

Answer 3

這是一個位掩碼 - 對於30個可能爲素數的8個值中的每一個，都有一位，所以每30個數字有8位。要將所有素數列表爲10^6，您需要8 * 10^6/30 = 2666667位= 33334個字節。

爲了解釋爲什麼這是一個好方法，你需要看看明顯的選擇。

一個更幼稚的方法就是使用位掩碼。你需要一百萬位，125000字節。

你也可以存儲素數的值。高達1000000，這些值適合20位，並且有78498個素數，所以這給出令人失望的1569960位（196245字節）。

另一種方法 - 儘管查找素數不太有用 - 但是要存儲每個素數和下一個素數之間的差異。低於一百萬，這符合6位（只要您記得那時素數都是奇數，所以您只需要存儲偶數差異並因此可以丟掉最低位），即470998位== 58874字節。 （你可以通過計算你需要跳轉多少個mod-30插槽來削減另外一點）。

現在，除了30 = 2 * 3 * 5之外，沒有什麼特別的30，所以這個查找實際上是在走你在開始之後立即通過Eratosthanes篩的掩模表示。你可以使用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個值。如果你用7塊30塊這樣做，你需要7×8 = 56位，所以這是一個小小的改進，但呃...幾乎沒有值得的麻煩。

所以這是更好的技巧之一，用於緊湊地存儲合理的小素數。有趣的是，如果素數隨機出現（但實際出現的相同數字達到1000000），則存儲在1和10^6之間數字的素數中的信息量將是〜0.397比特因此，在天真的信息理論假設下，你會認爲存儲第一百萬個素數的最好方法是使用1000000 * 0.397位或49609字節。）