如何減少Eratosthenes篩的空間複雜度以在a和b之間生成素數？

通過一些SO posts後，我發現Sieve of Eratosthenes是最好的生成素數的最快的方式&。如何減少Eratosthenes篩的空間複雜度以在a和b之間生成素數？

我想生成兩個數字之間的素數，比如a和b。在Sieve的方法中，AFAIK的空間複雜度爲O（b）。 PS：我寫了Big-O而不是Theta，因爲我不知道是否可以減少空間需求。

我們可以減少Sieve of Eratosthenes的空間複雜度嗎？

2012-09-14 Green goblin

這是最好的方法*爲某些a和b *。對於足夠大的數字來說，'b'字節或比特太大，還有其他方法。但是，儘管O（b）聽起來令人害怕，但它可能會讓你相當遠 - 如果每個數字使用一個位，一GB的內存應該使得b高達85億（比32位中的枚舉更多）！。 – delnan

是否存在一種方法，我需要一個等於a和b之間差距的空間？說，我們知道a和b之間的範圍。 –

不，因爲你必須知道從0到a的所有素數。否則，你不能運行篩子。 –

如果您有足夠的空間存儲sqrt（b）以上的所有素數，則可以使用額外的空間O（b-a）篩選範圍a到b中的素數。

在Python，這可能是這樣的：

def primesieve(ps,start,n): 
    """Sieve the interval [start,start+n) for primes. 

    Returns a list P of length n. 
    P[x]==1 if the number start+x is prime. 
    Relies on being given a list of primes in ps from 2 up to sqrt(start+n).""" 
    P=[1]*n 
    for p in ps: 
    for k in range((-start)%p,n,p): 
     if k+start<=p: continue 
     P[k]=0 
    return P

你可以很容易地使這種需要一半的空間僅篩分奇數。

來源

2012-09-14 20:18:56

Sorenson Sieve可能值得一看，如果空間複雜性真的是一個問題。從您分享的維基百科頁面獲得參考。

來源

2012-09-14 19:17:00

+1儘管索倫森並不是Eratosthenes的變體，但它是一個完全不同的篩子，具有更差的時間和更好的空間複雜性。 BTW根據賠率篩選可能會更糟糕，但它是O（1）額外的空間（除了輸出）。 :)我也加了一個關於它的答案。 :) –

在您最喜歡的搜索引擎上搜索「Eratosthenes分段篩」。如果你不想去搜索，我的博客上有一個implementation。

來源

2012-09-14 20:53:15 user448810

這裏有兩個基本的選擇：由以下sqrt(b)素數（在「偏移」sieve of Eratosthenes），或通過奇數篩的範圍[a..b]。那就對了;就像每個素數一樣，消除每個奇數的倍數。如果範圍過寬（如果塊太窄，效率可能會變差），則在一個塊中篩選範圍，或者在幾個「段」中篩選範圍。

在Haskell 可執行的僞代碼，

primesRange_by_Odds a b = foldl (\r x-> r `minus` [q x, q x+2*x..b]) 
           [o,o+2..b] 
           [3,5..floor(sqrt(fromIntegral b))] 
    where 
    o = 1 + 2*div a 2      -- odd start of range 
    q x = x*x - 2*x*min 0 (div (x*x-o) (2*x)) -- 1st odd multiple of x >= x*x in range

篩分通過賠率將具有O（1）附加空間複雜（輸出/範圍的頂部）。這是因爲，我們可以通過迭代加入 —不像埃拉託塞尼的篩的素數，下面sqrt(b)，爲此我們一定要預訂的O額外空間剛剛列舉的賠率（PI（SQRT（b））的） =〜2*sqrt(b)/log(b)（其中pi()是prime-counting function）。

來源

2012-09-19 15:20:42

如何減少Eratosthenes篩的空間複雜度以在a和b之間生成素數？

回答

相關問題