Biri bana Python numarası (2.7) tüm faktörler bulma verimli bir şekilde açıklayabilir mi?

Algoritmaları bu işi yapmak için yaratabilirim, ama kötü kodlanmıştır, ve çok uzun süre büyük bir sayı için sonuç yürütmek için alır bence.

def factors(n):    
    return set(reduce(list.__add__, 
                ([i, n//i] for i in range(1, int(n**0.5)   1) if n % i == 0)))

Bu nedenle, çok hızlı bir şekilde, Sayı 2 ** döner.

Neden üst sınır olarak karesel?

sqrt(x) * sqrt(x) = x. Eğer iki faktörün aynı ise, her iki kare kökü. Eğer bir faktör daha büyük yaparsanız, başka bir faktör daha küçük yapmak zorunda. Bu iki kişiden biri her zaman sadece o ana kadar iki eşleşen faktörlerin bir şey bulmak için var ya da sqrt(x), eşit veya daha az olacağı anlamına gelir. O x / fac1 fac2 almak için kullanabilirsiniz

reduce(list.__add__, ...) [fac1, fac2] küçük listelerini almak ve onları bir arada uzun bir liste katılıyor.

[i, n/i] for i in range(1, int(sqrt(n)) 1) if n % i == 0 döner bir çift etkenler ise kalan zaman ayırmak n küçük bir sıfır (yok gerek kontrol etmek için daha büyük bir tane, sadece alır ile bölme n küçük.)

Dışarıda set(...) çiftleri kurtuluyor. Bu sadece mükemmel kareler için olur bence. n = 4, Bu 2 iki kez döner, set içlerinden biri kurtulur.

Düzenleme:sqrt aslında **0.5 ama güzel olarak kendi kendine yeten bir parçacık olarak bırakıyorum hızlıdır.