SORU
23 Temmuz 2011, CUMARTESİ


Python ile bir dizi tüm faktörler bulma en etkili yolu nedir?

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.

CEVAP
23 Temmuz 2011, CUMARTESİ


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.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Andrey Menshikov

    Andrey Mensh

    28 Ocak 2012
  • InfoPuppet

    InfoPuppet

    15 Kasım 2011
  • Samvith V Rao

    Samvith V Ra

    20 EKİM 2006