超過python列表的大小

Question

我試圖在python中實現sieve of eratosthenes，但是當試圖找到所有素數達到sqare根的例如779695003923747564589111193840021時，我得到一個錯誤，說range（）的結果太多了項目。我的問題是，我如何避免這個問題，如果我用一個while循環實例化列表，我會得到一個錯誤，說我使用了太多的內存（甚至在它開始使用頁面文件之前），下面列出了兩個：

使用範圍（）

maxnum = 39312312323123123 

primes = [] 
seq = [] 
i = 0 
seq = range(2,maxnum) 

for i in seq: 
    mul = i * seq 
    for j in mul: 
     try: 
      seq.remove(j) 
     except: 
      pass 
     primes.append(i) 

print primes 

使用while：

maxnum = 39312312323123123 

primes = [] 
seq = [] 
i = 0 
while i < maxnum: 
    seq.append(i) 
    i+=1 

for i in seq: 
    mul = i * seq 
    for j in mul: 
     try: 
      seq.remove(j) 
     except: 
      pass 
     primes.append(i) 

print primes 

Answer 1

這是一個更復雜的算法，也許在技術上不計算爲篩子，但一個方法是不是馬上刪除一個給定的素數的倍數，但排隊的倍數（與總理一起）。這可以用於生成器實現。隊列仍然會包含許多（多個）素數，但不會像構建和過濾列表一樣多。手動完成，以顯示原理

前幾個步驟...

• 2是素數 - 屈服和隊列（4,2）
• 3是素數 - 屈服和隊列（6，3）
• 4是複合 - 取代（4,2）與（6,2）在隊列中
• 5是素數 - 屈服和隊列（10，5）
• 6是複合 - 取代（6，2）與（8,2）和（6,3）與（9,3）

注 - 隊列不是FIFO。您將始終提取具有最低第一項的元組，但是新/替換元組通常不具有最高的第一項和（如上面的6），將會有重複項。

爲了在Python中有效地處理隊列，我建議一個由元組的第一項鍵入的字典（即散列表）。數據是一組第二項值（原始素數）。

正如其他地方所建議的，在嘗試大型目標之前先測試小目標。如果你失敗，不要太驚訝。您可能仍然需要一次（在隊列中）需要太多的堆分配大整數來完成解決方案。直到你得到一個非常大的數量的素數

def getPrimes(maxnum): 
    primes = [] 
    for i in xrange(2, maxnum): 
     is_mul = False 
     for j in primes:   # Try dividing by all previous primes 
      if i % j == 0: 
       is_mul = True # Once we find a prime that i is divisible by 
       break   # short circuit so we don't have to try all of them 
     if not is_mul:   # if we try every prime we've seen so far and `i` 
      primes.append(i)  # isn't a multiple, so it must be prime 
    return primes 

你不應該耗盡內存：

Answer 2

我會說， 「使用xrange()，而不是」，但是你實際上是使用int作爲篩結果列表中.. ...所以一個整數發生器不是一個正確的解決方案。

不管你用什麼函數來做這件事，我認爲很難實現一個包含39312312323123123元素的列表......畢竟，這是279PB的64位整數。

試試這個。

class FoundComposite(Exception): pass 

primes = [2] 

seq = itertools.takewhile(  # Take integers from a list 
      lambda x: x<MAXNUM,  # until we reach MAXNUM 
      itertools.count(2)  # the list of integers starting from 2 
     ) 

#seq = xrange(2, MAXNUM)   # alternatively 

for i in seq: 
    try: 
     for divisor in primes: 
      if not (i % divisor): 
       # no remainder - thus an even divisor 
       # continue to next i in seq 
       raise FoundComposite 
     # if this is reached, we have tried all divisors. 
     primes.append(i) 
    except FoundComposite: 
     pass 

Answer 3

range()返回包含在所請求的範圍中的所有編號的列表，而xrange是發電機，併產生相繼與存儲器消耗接近於零的數目之一。

Answer 4

您的算法已損壞。首先讓它爲maxnum = 100工作。

一旦你得到它的工作，你會發現maxnum = 100000000將需要很長的時間來運行。

情節花費MAXNUM在運行時間（10,100,1000,10000,100000,1000000 ...）你可以推斷多久39312312323123123將採取:)

Answer 5

關於內存限制，如何創建一個內部是列表或數組的鏈表的自定義列表（類）。神奇地從一個內部遍歷到另一個，並根據需要添加更多內容，因爲調用者使用您提供的外部接口的自定義列表，這些外部接口將類似於促進.append .remove等需要的成員在你的問題中使用的數組。

注意：我不是Python程序員。不知道如何實現我在Python中所說的內容。也許我不知道這裏的背景，所以我會理解我是否被拒絕。

也許使用「generators」，因爲它們在python中調用時會產生內部列表的結果，就好像它是一個巨大的單個列表。可能與linked list。

Answer 6

有一個叫gmpy

它有幾個功能，因爲它們是非常快的，可能對你有用的Python第三方模塊。概率性的東西在40億大關左右。

next_prime(...) 
    next_prime(x): returns the smallest prime number > x. Note that 
    GMP may use a probabilistic definition of 'prime', and also that 
    if x<0 GMP considers x 'prime' iff -x is prime; gmpy reflects these 
    GMP design choices. x must be an mpz, or else gets coerced to one. 

is_prime(...) 
    is_prime(x,n=25): returns 2 if x is _certainly_ prime, 1 if x is 
    _probably_ prime (probability > 1 - 1/2**n), 0 if x is composite. 
    If x<0, GMP considers x 'prime' iff -x is prime; gmpy reflects this 
    GMP design choice. x must be an mpz, or else gets coerced to one. 

Answer 7

試試這個。這樣您就不必擔心創建倍數列表。不知道這是否仍然算篩。

其實，這不適用於maxnum = 39312312323123123。使用Prime number theorem我們可以估計在該範圍內會有大約1,028,840,332,567,181素數。

正如在this question中指出的那樣，32位系統上的python列表的最大大小爲536,870,912。所以即使你沒有耗盡內存，你仍然無法完成計算。

儘管如此，您應該沒有64位系統的問題。

2 ** 64 => 18446744073709551616

從上述問題(2 ** 64)/8使用數學，列表中元素的最大數量是2,305,843,009,213,693,951比你會遇到的素數的估計數。

編輯：

爲了避免內存問題，你可以在你的素數的列表存儲在硬盤上的文件。每行存儲一個素數並在每次檢查新數字時讀取文件。

也許是這樣的：

primes_path = r'C:\temp\primes.txt' 

def genPrimes(): 
    for line in open(primes_path, 'r'): 
     yield int(line.strip())  

def addPrime(prime): 
    primes_file = open(primes_path, 'a') 
    primes_file.write('%s\n' % prime) 
    primes_file.close() 

def findPrimes(maxnum): 
    for i in xrange(2, maxnum): 
     is_mul = False 
     for prime in genPrimes(): # generate the primes from a file on disk 
      if i % prime == 0: 
       is_mul = True  
       break    
     if not is_mul:   
      addPrime(i) # append the new prime to the end of your primes file 

最後，你必須包含所有的素數的硬盤驅動器上的文件。

好的，所以這會很慢，但你不會用完內存。您可以通過提高讀取/寫入文件的速度來加快速度（如RAID）。