數據與素數成比例的素數篩的空間複雜度是多少？

我正在練習爲空間或時間複雜度優化的編寫算法。使用主篩時，至少必須存儲所有找到的素數列表。似乎數據與所發現的素數的數量成比例，是算法可能使用的最小空間量。數據與素數成比例的素數篩的空間複雜度是多少？

此理由是否有效？
該算法的空間複雜度如何評估？

From Wikipedia about the sieve of Atkin - 我不確定的是當質數超過這個數時，篩子如何使用O（n^1/2）空間。這就是爲什麼看起來至少空間必須與素數成正比的原因。我是否將可數數字與空間複雜性相混淆？

In this paper on the sieve of Atkin，他們的算法打印「素數達到N ...這裏」內存「不包括打印機使用的紙張。」這似乎是對空間的不公平計算。

我希望澄清一下，應該如何/實際上客觀衡量。

。

def prime_sieve(limit): 
    factors = dict() 
    primes = [] 
    factors[4] = (2) 
    primes.append(2) 
    for n in range(3, limit + 1): 
     if n not in factors: 
      factors[n * 2] = (n) 
      primes.append(n) 
     else: 
      prime = factors.get(n) 
      m = n + prime 
      while m in factors: 
       m += prime 
      factors[m] = (prime) 
      del factors[n] 
    return primes

來源

2014-10-20 12345678910111213

請不要在問題中添加新問題 - 它會使現有答案失效。每個問題應該只包含一個問題;如果你有更多，請多詢問一下。你已經有兩個解決問題的不同部分的答案，那麼你如何決定哪一個應該成爲「答案」呢？ – jonrsharpe 2014-10-20 11:17:24

這是一個很好的觀點。 Idk在這裏是否適合打破有關阿特金紙的問題......？ @larsmans解釋說，我的算法與論文的算法有根本的不同，這就是爲什麼他們有不同的複雜性。 – 12345678910111213 2014-10-20 11:42:53

在這一點上會有點困難，雖然你可以問* larsmans *他們是否會介意在一個新問題上重複他們的答案。 – jonrsharpe 2014-10-20 12:32:41

該算法的空間複雜度爲len(numbers) + len(primes);列表的大小加上字典的大小。

在這種情況下，該算法是差比你期望的一個天真的總理篩（limit）。 len(numbers) + len(primes) > limit，因爲例如對於prime_sieve(100)以下無關號碼存儲在numbers：

{129: 43, 134: 67, 141: 47, 142: 71, 146: 73, 158: 79, 166: 83, 178: 89, 194: 97, 102: 17, 104: 2, 105: 3, 106: 53, 110: 11, 111: 37, 112: 7, 114: 19, 115: 23, 116: 29, 117: 13, 118: 59, 120: 5, 122: 61, 123: 41, 124: 31}

有幾個質數篩，用不同的時間和空間複雜度;見例如Wikipedia和問題，如How do i reduce the space complexity in Sieve of Eratosthenes to generate prime between a and b?

另外，還要注意有沒有必要prime = numbers.get(n) - 你已經檢查if n not in numbers，所以你可以只使用prime = numbers[n]。

來源

2014-10-20 10:15:29 jonrsharpe

維基百科有關Atkin篩 - 我不確定的是當質數超過這個數時，篩可以如何使用O（n^1/2）空間。這就是爲什麼看起來至少空間必須與素數成正比的原因。我是否將可數數字與空間複雜性相混淆？ – 12345678910111213 2014-10-20 10:30:09

@mattkaeo我不知道細節，但是[Atkin的Sieve的Wiki頁面]（http://en.wikipedia.org/wiki/Sieve_of_Atkin）鏈接到[本文]（http：//www.ams .ORG /期刊/ MCOM/2004-73-246/S0025-5718-03-01501-1/S0025-5718-03-01501-1.pdf）。 – jonrsharpe 2014-10-20 10:35:11

在論文中，它表示他們在空間計算中不包含素數......「打印質數最高爲 N ...這裏的」內存「不包括打印機使用的紙張。」這看起來不公平 – 12345678910111213 2014-10-20 10:58:54

空間複雜性測量是完全公平的。如果用yield n代替primes.append(n)，並且您在消費者例程中逐個處理素數而不存儲它們，例如找到具有特定屬性的素數，則素數本身所需的存儲空間爲O（1），用質數來衡量。

（yield是構建發生器的Python的方式，發射值給調用者和類型協同例程的保存功能的狀態，以便它可以被重新輸入。）

來源

2014-10-20 11:07:42

「
」對於主篩子，至少必須存儲所有找到的質數列表。「

錯誤。您只需要低於（包括）您的上限的平方根的素數，以篩選該範圍內的素數。

如果您的篩子是增量式的，無限的，那麼您只需要在當前生產點的平方根以下（並且包括）有素數。

這怎麼可能？通過使用單獨的爲「核心」素數（那些低於sqrt）的素數提供，這是完全可以用遞歸計算的相同函數。有關示例，請參閱this answer。

而且它是完全合法的不計較產生質數 - 你可以確實將它們發送到打印機，或外部文件等，所以，這樣的篩的空間複雜度會O(sqrt(N)/log(N)) ~ O(sqrt(n/log(n)))爲ñ素數最多N〜= n * log n。

另外，不要靠近阿特金的篩子。在街上的字是，它是不可能的擊敗正確的輪Eretosthenes篩它（尋找答案GordonBGood在這個問題上，如this one）。

來源

2014-10-20 21:25:34

數據與素數成比例的素數篩的空間複雜度是多少？

回答

相關問題