埃拉托色尼的篩（減少空間複雜度）

Question

我想兩個給定數字之間生成素數「A」和「B」（B> A）。我所做的是將布爾值存儲在大小爲b-1（即數字至b）的數組中，然後應用篩選方法。

有沒有更好的辦法，減少空間的複雜性，如果我不從至b需要的所有質數？

Answer 1

您需要存儲小於等於b的平方根的所有素數，然後對於a和b之間的每個數字，檢查它們是否可以被這些數字中的任何一個整除，並且它們不等於這些數字。所以在我們的情況下，幻數是sqrt（b）

Answer 2

您可以使用Eratosthenes的分段篩。基本的想法很簡單。

在一個典型的篩子中，我們從大量的布爾值開始，將所有值設置爲相同的值。這些代表奇數，從3開始。我們看第一個，看看它是真的，所以我們將它添加到素數列表中。然後，我們將該數字的每個倍數標記爲不是素數。

現在，問題在於它不是非常緩存友好的。當我們標出每個數字的倍數時，我們會遍歷整個數組。然後當我們到達最後時，我們從頭開始（不再在緩存中）並再次遍歷整個數組。每次通過數組時，我們再次從主存儲器中讀取整個數組。

對於分段篩，我們做的事情有點不同。我們首先發現只有我們關心的極限的平方根的質數。然後我們使用這些來標記主數組中的素數。這裏的區別是訂單其中我們標記了質數。而不是標出全部三個倍數，然後是所有倍數5，依此類推，我們首先標記適合緩存的數據的三倍。然後，我們回過頭去標記適合緩存的數據的五個倍數，而不是繼續增加數組中的數據。然後是7的倍數，依此類推。然後，當我們標記出該緩存大小的數據塊中的所有倍數時，我們轉向下一個緩存大小的數據塊。我們首先在這個塊中標記3的倍數，然後是5的倍數，依此類推，直到我們標記出該塊中的所有倍數。我們繼續這種模式，直到我們標出所有塊中的所有非素數，然後我們完成了。

因此，如果N個素數低於我們關心的極限的平方根，那麼一個幼稚的篩子將讀取整個布爾數組的N次。相比之下，分段篩只會讀取每個數據塊的一次。一旦從主存儲器讀取大塊數據，在從主存儲器讀取更多數據之前，該塊上的所有處理完成。

這給出的確切加速將取決於緩存的速度與主內存的速度的比率，您使用的陣列的大小與緩存的大小等等。儘管如此，它通常是相當可觀的 - 例如，在我的特定機器上，尋找高達1億的質量，分段式篩具有大約10：1的速度優勢。

有一點你必須記住，如果你使用的是C++。std::vector<bool>的一個衆所周知的問題是在C++ 98/03下，vector<bool>被要求是一種專門化，它將每個布爾值存儲爲一個單獨的位，並帶有一些代理欺騙以獲得類似於bool的行爲。這項要求從此被解除，但許多圖書館仍然包括它。

對於非分段篩，通常是一種有用的折衷。雖然它需要一些額外的CPU時間來計算掩碼，並且一次只修改一個位，但它可以爲主內存節省足夠的帶寬，而不僅僅是補償。使用分段篩，主內存的帶寬幾乎不是一個很大的因素，所以使用vector<char>通常似乎會給出更好的結果（至少在我使用編譯器和處理器的情況下）。從分段篩獲得最佳性能確實需要知道處理器緩存的大小，但要正確地獲得它的正確性通常並不重要 - 如果您認爲其大小比實際小，則不會必須最大限度地利用你的緩存，但你通常不會失去很多。