Was ist "uncaught signal # 9"? TextMate, Python, MacOS

Question

Ich lerne gerade, in Python zu programmieren und wirklich zu genießen, Projekt Euler durchzugehen und die Probleme zu versuchen. Ich bin auf Problem # 3, das uns fragt, den größten Primfaktor von 600851475143 zu finden. Ich habe den Code unten geschrieben, um dies zu tun, und es funktioniert gut für kleinere Werte, bis 540995 getestet, aber sobald ich versuche, es los zu setzen 600851475143, bekomme ich eine Fehlermeldung:

Program terminated by uncaught signal #9 after 50.95 seconds.

ich dies auf Textmate mit Python 2.7.13 auf einem Mac schreibe 10,12 OS ausgeführt wird. Google hat mir nicht geholfen, eine Lösung dafür zu finden. Ich würde jede Einsicht schätzen. Hier

ist der Code, den ich ausführen:

n = 600851475143 
fList = [] 
pList = [] 

# factor n starting with largest factor 
for i in range(n-2, 2, -2): 
    # if prime factor list is empty 
    if len(pList) == 0: 
     if n % i == 0: 
      factor = i 
      # as a factor is found, test for primality 
      for k in range(factor-2, 2, -2): 
       if factor % k == 0: 
        if factor not in fList: 
         fList.append(factor) 
      if factor not in fList: 
       pList.append(factor) 
print(pList) 

Vielen Dank für Ihre Einsichten!

Answer 1

Sie haben nicht genügend Arbeitsspeicher. Also funktioniert Ihre Lösung bis zu 540995, was eine relativ kleine Zahl im Vergleich zu 600851475143 ist. Denken Sie daran, dass Sie eine verschachtelte Schleife machen, so dass die Laufzeit Ihres Algorithmus O(n)^2 ist. Mit anderen Worten, Ihre Schleifen laufen sehr oft. Sie können mehr über algorithmische Komplexität here finden. Das hier wird gesagt, wie ich das Problem

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

Hoffnung würde Ansatz, und viel Glück hilft :)