Wie große Zahlen in Python

Question

Mein Problem zu handhaben ist den größten Primfaktor von 600851475143.

-Code zu finden:

class Prime: 
    def isPrime(self,n): # Checks if number is prime 
     number=n   
     flag=0 
     #code to exclude 1 nd 2 from check 
     if number==1: 
      return False 
     elif number==2: 
      return True 
     #code to loop through and check if number is divisible  
     for i in range(2,(number/2)+1): 
      if (number)%i==0: 
       flag=1 
       break 
      else: 
       flag-0 
       continue 
     #code to return result 

     if flag==0: 
      return True 
     elif flag==1: 
      return False 

Aber dieser Code löst einen Überlauf-Fehler - „OverflowError: range() Ergebnis hat zu viele Gegenstände ". Was kann ich tun, um eine große Anzahl zu bewältigen?

Ich versuchte mit n = int(raw_input()) wie in "Python long integer input", vorgeschlagen, aber kein Glück!

def main(): 
    p=Prime() 
    n = int(raw_input()) 
    print p.isPrime(n) 

Answer 1

Das Problem ist die Menge der Zahlen, nicht die Größe. Sie bauen ein range Objekt für 600851475143/2 Elemente. Einzelwort-Ganzzahlen würden dafür mehr als ein Terabyte Speicher verbrauchen. Da Sie große Ganzzahlen verwenden, verbrauchen Sie noch mehr Speicher. Wie viel Adressraum haben Sie Sie haben?

Reduzieren Sie die Größe der benötigten Elemente. Zuallererst müssen Sie nur durch die Quadratwurzel der Zahl überprüfen, um die Primfaktorzerlegung zu vervollständigen. Zweitens müssen Sie keinen Generator erstellen: Erhöhen Sie einfach eine Variable und eliminieren Sie die Struktur vollständig. Schließlich müssen Sie nur durch Primzahlen dividieren, nicht alle Zahlen.

Erster Schritt:

for i in range(2, int(math.sqrt(number))+1): 
    while number % i == 0: 
     number = number // i 
     largest = i 

Wenn Sie fertig sind, der größte Primfaktor desto größer ist der number und largest ist.

Zweiter Schritt:

konvertieren, den großen range Ausdruck einen einfachen Variablen Schritt:

i = 2 
upper = int(math.sqrt(number) + 1) 
while i < upper: 
    while number % i == 0: 
     number = number // i 
     largest = i 
    i +=1 

Sie können dies 2x beschleunigen, indem nur 2 und dann die ungeraden Zahlen zu tun.

Algorithmus Verbesserung:

Bauen Sie ein Sieb oder ein anderes Verfahren, um zu verfolgen Primzahlen. Iteriere durch diese statt durch alle Ganzzahlen.