Euler Projekt # 3 in Python

Ich versuche, das Projekt Euler Problem 3 in Python zu lösen:

The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ? 

Ich weiß, mein Programm ist ineffizient und überdimensioniert, aber ich wollte nur wissen, warum funktioniert es nicht? Hier ist der Code:

 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) 

Und hier ist der Fehler:

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

4 Solutions collect form web for “Euler Projekt # 3 in Python”

Der Grund dafür ist, dass eine Liste in Python auf 536.870.912 Elemente begrenzt ist (siehe Wie Big ein Python Array Get? ) Und wenn Sie den Bereich in Ihrem Beispiel erstellen, überschreitet die Anzahl der Elemente diese Zahl und verursacht den Fehler.

Der Spaß von Project Euler ist herauszufinden, das Zeug auf eigene Faust (was ich weiß, dass du tust :)), so werde ich einen sehr kleinen Hinweis geben, der diesen Fehler umgehen wird. Denken Sie darüber nach, was ein Faktor einer Zahl ist – Sie wissen, dass es für 600851475142 unmöglich ist, ein Faktor von 600851475143 zu sein. Deshalb müssten Sie nicht den ganzen Weg bis zu dieser Nummer überprüfen. Nach dieser Logik, gibt es eine Möglichkeit, können Sie deutlich reduzieren die Reichweite, die Sie überprüfen? Wenn Sie ein bisschen Forschung in die Eigenschaften der primären Faktoren zu tun, können Sie etwas Interessantes finden 🙂

Zuerst im ersten Codeblock nicht i = i+1 da die for-Schleife sich darum kümmert. Zweitens verwenden Sie xrange , um einen Generator anstelle einer Liste zu xrange .

Das ist der Code, den ich benutzt habe !!

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

-M1K3

@ Seamonkey8: Ihr Code kann verbessert werden. Du kannst mich um 2 anstatt eins erhöhen. Es macht einen Geschwindigkeitsunterschied für wirklich hohe Zahlen:

 n,i = 6008514751231312143,2 while i*i <= n: if n%i == 0: n //= i else: i+=[1,2][i>2] 
Python ist die beste Programmiersprache der Welt.