Python: Finde die zwei Primfaktoren einer Zahl. Wie kann man diesen Code effizienter machen?

Question

Mein aktueller Code:

import math 
def factorMe(value): 
last = int(math.sqrt(value)+1) 
for i in range(2,last): 
    if value %i ==0: 
     return (i,int(value/i)) 

Mein Code kann die meisten Testfall treffen; Aber wenn die Eingabe 603091532958059 ist, lautet die Antwort (24557917, 24557927); Aber es dauert mehr als 1 Sekunde zu beenden (Zeitlimit überschritten);

Irgendwelche Vorschläge? Vielen Dank!

Answer 1

Um Ihren Code zu beschleunigen, könnten Sie Fermat's factorization method verwenden, wie @PM 2Ring in Kommentaren erzählt. Versuchen Sie folgenden Code

import math 
def factorMe(value): 
    last = int(math.sqrt(value)+1) 
    # check if value is even 
    if value % 2 == 0: 
     return (2, int(value/2)) 
    # value is odd number 
    a = int(math.sqrt(value)) + 1 
    b2 = int(a * a - value) 
    b = int(math.sqrt(b2)) 
    while b ** 2 != int(b2): 
     a += 1 
     b2 = a * a - value 
    return (int(a - math.sqrt(b2)), int(a + math.sqrt(b2))) 


v = 603091532958059 
%timeit r = factorMe(v) 
print(r) 

100000 loops, best of 3: 2.15 µs per loop 
(24557917, 24557927)