Optimierung des Factoring-Programms

Question

Dies ist mein Faktorisierungscode, der verwendet wird, um alle Faktoren einer Zahl zu finden, aber nach ungefähr 7 Stellen beginnt das Programm zu verlangsamen.

Ich frage mich, ob es eine Methode gibt, dieses Programm zu optimieren, damit es Zahlen schneller faktorisieren kann.

number = int(input("Input the whole number here?\n")) 
factors = [1] 

def factorization(): 
    global factors 
    for i in range(1 , number): 
     factor = (number/i) 
     try: 
      factorInt = int(number/i) 
      if factorInt == factor: 
       factors.append(factorInt) 
     except ValueError: 
      pass 


factorization() 
print(factors) 

Answer 1

Die effektivste Optimierung ist mit der Feststellung, dass, wenn die Zahl nicht triviale Faktoren hat, und die kleinste von ihnen ist kleiner als die Quadratwurzel der Zahl, und es besteht keine Notwendigkeit, weiterhin Schleife über diese Quadratwurzel.

Tatsächlich sollte dieser kleinste Faktor m sein. Wir haben n = m.p und der andere Faktor ist so, dass p >= m. Aber wenn m > √n, dann m.p >= n, ein Widerspruch.

---

Beachten Sie, dass diese Optimierung nur beschleunigt-up die Verarbeitung von Primzahlen (für die Verbund diejenigen, stoppt die Suche vor √n sowieso). Aber die Dichte der Primzahlen und die Tatsache, dass n ist viel größer als √n machen es absolut wert.

---

Eine weitere Optimierung ist mit der Feststellung, dass der kleinste Teiler eine Primzahl sein muss, und Sie können eine gespeicherte Tabelle der Primzahlen verwenden. (Es gibt weniger als 51 Millionen Primzahlen unter einer Milliarde.) Die Beschleunigung wird weniger auffällig sein.

Answer 2

Lassen Sie mich eine NumPy-basierte Lösung anbieten. Es scheint sehr effizient:

import numpy as np 

def factorize(number): 
    n = np.arange(2, np.sqrt(number), dtype=int) 
    n2 = number/n 
    low = n[n2.astype(int) == n2] 
    return np.concatenate((low, number // low,)) 

factorize(34976237696437) 
#array([  71, 155399, 3170053, 492623066147, 225073763,  11033329])]) 
# 176 msec