分割如何提高Eratosthenes篩的運行時間？

Question

我遇到了Eratosthenes篩的分段實現，它承諾運行速度比傳統版本快很多倍。 有人可以解釋如何細分改善運行時間？ 請注意，我想查找[1，b]中的素數。

它適用於這樣的觀念：（尋找素數，直到10^9）

• 我們首先生成這是需要跨斷倍數低於開方篩分素數（10^9） 。然後我們開始交叉第一個素數2的倍數，直到我們達到2> = segment_size的倍數，如果發生這種情況，我們使用（multiple-segment_size）計算下一個分段中該倍數的索引並將其存儲在單獨的數組（下一個[]）。然後，我們使用相同的程序將下一個篩選素數的倍數分離。一旦我們將第一個區段中所有篩分素數的倍數交叉，我們遍歷篩選數組並打印（或計數）素數。

• 爲了篩選下一個段，我們重置篩數組，並且通過segment_size遞增較低的偏移量。然後我們再次啓動渡客的倍數，每個篩分總理，我們從下一個數組檢索篩指標，我們開始穿越過倍數從那裏...

Answer 1

分段篩做所有的與常規篩相同的操作，所以大O時間複雜度不變。區別在於使用內存。如果篩子足夠小以適應記憶，則沒有區別。隨着篩網尺寸的增加，參考地點成爲一個因素，因此篩分過程變慢。在極端情況下，如果篩網不適合內存並且必須分頁到磁盤，篩選過程將變得非常緩慢。分段篩保持內存大小不變，並且可能很小，因此篩的所有訪問都是局部的，因此速度很快。

Answer 2

即使篩子完全適合RAM，訪問的地點仍然有很大的差異。一個C++實現的賠率只Eratosthenes需要幾乎半分鐘篩選前2^32的數字;在我的老化Nehalem中，256K字節的二級緩存只需要8.5秒就可以完成同樣的初始化小256K字節段（2^21位，代表2^22個數）的篩選。

從小型高速緩存友好段中篩選的加速在該範圍的較高區域中減少，因爲篩選必須每次迭代所有高達sqrt（n）的因子，而不管其大小段是。對於接近2^64的片段，其中小因素包括203,280,221個素數（即完整的32位篩）最爲顯着。儘管如此，分段操作仍然能夠完全完成篩分。您可以篩選接近2^64的片段，以達到每秒數百萬個素數的調整，在較低的區域每秒數千萬。這是在計算素數，而不是原始數量的礦石。即使你擁有大量的記憶，全篩仍然不能超過2^32左右。