歐拉項目在Python

＃3

我試圖解決項目歐拉問題3在Python：歐拉項目在Python

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

What is the largest prime factor of the number 600851475143 ?

我知道我的計劃是低效和超大的，但我只是想知道爲什麼它不工作？下面的代碼：

def check(z): 

# checks if the given integer is prime 

    for i in range(2, z): 
     if z % i == 0: 
      return False 
      break 
     i = i+1 
    return True 

def primegen(y): 
# generates a list of prime integers in the given range 

    tab = [] 
    while y >= 2: 
     if check(y) == True: 
      tab.append(y) 
     i = i-1 


def mainfuntion(x): 
# main function; prints the largest prime factor of the given integer 

    primegen(x) 
    for i in range(len(tab)): 
     if x % tab[i] == 0: 
      print tab[i] 
      break 

mainfuntion(600851475143)

而這裏的錯誤：

for i in range(2, z): 
OverflowError: range() result has too many items

來源

2012-11-21 user1843479

您在'primegen'中混合了'i'和'y'。至於錯誤，請嘗試'xrange'。 –

像你在做的那樣，在'mainfunction'裏面引用變量'tab'是個壞習慣。你對'primegen（）'的調用可以返回素數列表，你可以給一個變量賦值：'primes = primegen（x）'，然後下一行'for xrange（len（primes））'。 – jozzas

歡迎來到Stackoverflow。我爲你格式化了代碼，但請看看[this]（http://stackoverflow.com/editing-help）和[this]（http://meta.stackexchange.com/a/22189），以及格式化代碼塊下次正確。 – BrtH

的原因是，在Python列表限制爲536,870,912元（見How Big can a Python Array Get?），當你在你的例子創建範圍，元素的數量超過了這個數字，導致錯誤。

歐拉計劃的樂趣是自己弄清楚這些東西（我知道你在做:)），所以我會給出一個非常小的暗示來繞過這個錯誤。考慮一個數字的因素是什麼 - 你知道600851475142是600851475143的因素是不可能的。因此，你不必檢查一直到那個數字。遵循這個邏輯，是否有一種方法可以顯着減少你檢查的範圍？如果您對素數因素的屬性進行了一些研究，您可能會發現一些有趣的內容:)

來源

2012-11-21 22:56:04 RocketDonkey

您可以取代範圍由xrange不將整個元素列表存儲在內存中。 – barracel

非常感謝！ – user1843479

@barracel確實:)我將在短短一分鐘內（在會議中:)添加更新） – RocketDonkey

首先，在第一個代碼塊中，不要使用i = i+1，因爲for循環會處理它。其次，使用xrange來生成一個生成器而不是一個列表。

來源

2012-11-21 23:07:14

這是我使用的代碼！

n = 600851475143 
i = 2 
while i * i < n: 
    while n % i == 0: 
     n = n/i 
    i = i + 1 

print n

-M1K3

來源

2013-03-02 02:59:46 seamonkey8

@ seamonkey8：您的代碼可以得到改善。你可以增加2而不是1。它對真的很高的數字會產生速度差異：

n,i = 6008514751231312143,2 

while i*i <= n:  
    if n%i == 0: 
     n //= i 
    else: 
     i+=[1,2][i>2]

來源

2014-12-13 16:47:51

歐拉項目在Python

回答

相關問題