內存錯誤而使用python

Question

我試圖找出一個大數目的最大素數，計算最大素因子，當我運行此我碰到一個錯誤說：

回溯（最近通話最後一個）： 文件 「prb3.py」，第45行，在 打印prime_factor（） 文件 「prb3.py」，第12行，在prime_factor 在範圍n（2，i）的： 的MemoryError

它正常工作時我用小號碼跑13195

""" 
Problem: 

The prime factors of 13195 are 5, 7, 13 and 29. 

What is the largest prime factor of the number 600851475143 ? 
""" 
import math 
def prime_factor(): 
     i=600851475143 
     factors=[] #list stores all the factors of a number 
     for n in range(2,i): 
       if(i%n==0 and (n%2!=0 and n!=2)): 
         factors.append(n) 

     """ 
     Now I have all the factors(which are not even numbers) 

     Next step is to find prime number from factors list 
     """ 

     for factor in factors: 
       sqr_root=int(math.sqrt(factor)) 
       """ 
       I take a factor from list and divide it by numbers from 3 
       to sqroot(factor-1).If I get a 0 as remainder I consider it 
       as non prime and remove from the list.I apply this only to 
       factors whose sqr root is greater than 3.If it is less than 
       3 I divide it by each number between 3 and factor-1. 
       """ 
       if(sqr_root<=3): 
         for num in range(3,factor-1): 
           if(factor%num==0): 
             factors.remove(factor) 
             break 
       else: 
         for num in range(3,sqr_root): 
           if(factor%num==0): 
                                  1,1   Top 
     return len(factors) 


if __name__ == "__main__": 
     print prime_factor() 

Answer 1

在Python2中，range()返回一個列表。在你的情況下，列表將包含600851475141 int對象。由於列表如此之大，所以不能適應你的記憶，所以你得到那個記憶錯誤

因爲你並不真的需要所有這些數字在同一時間內存，你可以嘗試使用xrange()來代替。

我認爲你可以通過將你找到的因素分開來簡化你的問題。例如。

for n in xrange(2, i): 
     while(i % n == 0 and (n % 2 != 0 and n != 2)): 
      i /= n 
      print n 
     if i == 1:  
      break 

不需要循環600851475141周時間應該使你的程序要快得多