Python「OverflowError」

Question

我剛開始學習使用Python編寫代碼。我嘗試寫一些代碼來回答這個項目歐拉問題：

的13195的首要因素是5，7，13和29

號碼是多少600851475143的最大質因數？

我的程序與13195的測試用例一起工作，但是當我嘗試輸入600851475143時，出現錯誤：「OverflowError：range（）結果有太多項目」 有誰知道我該如何解決這個問題？

這裏是我的代碼：

class Euler3: 
    "A class to find the largest prime factor of a given number" 
    n = 600851475143 
    primeFactors = [] 
    for i in range(2,n): 
     if (n%i ==0): 
      primeFactors.append(i) 
      n = n/i 
      i = i -1 #reset i 
    print primeFactors 

任何幫助或建議，將不勝感激！

Answer 1

我猜你正在使用python 2而不是python 3 - range(2,n)實際上構造了一個列表！你沒有足夠的內存來存儲6000億個數字！儘管如此，xrange應該沒問題。

此外，您的想法i=i-1不起作用。 For循環不能像C一樣工作，並且這個hack只能在C樣式循環中工作。 for循環遍歷range(2,n)。如果i一次迭代獲得值5，那麼無論您對i做什麼，下次仍會獲得6。

另外，列表range(2,n)是在您輸入循環時構造的。所以當你修改n時，那不會改變任何東西。

你將不得不重新思考你的邏輯了一下。

（如果你不相信我的話，請嘗試使用175作爲測試用例）

作爲最後的評論，你或許應該得到使用特殊整數除法的習慣：n = n // i。儘管/和//在python 2中的工作方式相同，但這確實是不推薦的行爲，並且它們在python 3中的工作方式不同，其中/會給你一個浮點數。

Answer 2

您可以通過使用xrange代替range

你的下一個問題將是該計劃花費了太多的時間來運行，因爲你需要一些條件

一個下打出來的循環解決問題更好的方式來處理重複的因素是有while

 while (n%i ==0): 
     primeFactors.append(i) 
     n = n/i 

Answer 3

的range函數創建一個列表和TR更換if將它存儲在內存中。長時間創建一個列表是導致OverflowError的原因。您可以使用xrange來獲得一個可根據需要生成數字的發生器。

這就是說，我認爲你會發現你的算法對於計算大素數太慢了。有許多素數算法，但我可能會建議檢查出Sieve of Eratosthenes作爲起點。

編輯：正確xrange實際上不會返回一個生成器，而是一個xrange對象，其行爲很像一個生成器。我不確定你是否在意，但是這讓我很不高興！

Answer 4

n = 600851475143 
primeFactors = [] 
for i in range(2,n): 

我想你可以注意到，

for i in range(2,n): 

您可以通過

range(2,int(sqrt(n))+2) 

更換

range(2,n) 

，因爲你可以看到維基優化功能.. 。

Answer 5

我正在與這個Python「OverflowError」作鬥爭，在這個項目上工作。我試圖想出一個有效的組合。

但是，我確實發現了一個聰明的東西，至少我認爲是這樣:)，這樣做。

這是我對這個問題的代碼。

def IsNumberPrime(n): 
    bounds = int(math.sqrt(n)) 
    for number in xrange(2,bounds+2): 
     if n % number == 0: 
      return False 
    return True 

def GetListOfPrimeFactors(n): 
    primes = [] 
    factors = GetListOfFactors(n) 
    if n % 2 == 0: 
     primes.append(2) 

    for entries in factors: 
     if IsNumberPrime(entries): 
      primes.append(entries) 
    return primes 


GetListOfPrimeFactors(600851475143) 

def GetListOfFactors(n): 
    factors = [] 
    bounds = int(math.sqrt(n)) 
    startNo = 2 

    while startNo <= bounds: 
     if n % startNo == 0: 
     factors.append(startNo) 
     startNo += 1 
    return factors 

我所做的是將輸入的數字的因子輸入到「因素」列表中。在那之後，我列出了一系列因素，並確定哪些是素數，並將它們存儲到打印的列表中。

我希望這有助於

邁克 -

Answer 6

這是尋找素數，我已經迄今爲止發現的最好的方式，這花了我大約5秒獲得

def isprime(n): 
    #make sure n is a positive integer 
    n = abs(int(n)) 
    #0 and 1 are not primes 
    if n < 2: 
     return False 
    #2 is the only even prime number 
    if n == 2: 
     return True 
    #all other even numbers are not primes 
    if not n & 1: 
     return False 
    #range starts with 3 and only needs to go up to the square root of n 
    #for all odd numbers 
    for x in range (3, int(n**0.5)+1, 2): 
     if n % x == 0: 
      return False 
    return True #if it makes it through all the catches, it is a prime 

Answer 7

答案。

import math 

def is_prime_number(x): 
    for i in range(int(math.sqrt(x)), 2, -1): 
     if x % i == 0: 
     return False 
    return True 

def next_prime_number(number): 
    #Returns the next prime number. 
    if number % 2 == 0 and number != 2: 
     number += 1 
    while not is_prime_number(number): 
     number += 2 
    return number 

num = 600851475143 
i = 2 
while (i < long(math.sqrt(num)/2)): 
    if num % i == 0: 
     largest = i 
     print largest 
    i = next_prime_number(i + 1) 

Answer 8

的xrange不會可能會幫助你（或者它可能！），但這裏的關鍵是要reliaze，你不需要找了素數至600851475143或600851475143的因素，但它的首要因素，所以... 使用好老因式分解法，像這樣：

A=600851475143 
n=2 
fac=[] 
while(n<=int(A)): 
    B=1 
    while(A%n==0): 
     B=0 
     A=A/n 
    if(B==0): 
     fac.append(n) 
    n=n+1 

print max(fac) 

這將返回幾乎立即