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

  • Distractify

    Distractify

    1 Aralık 2011
  • Julian Smith

    Julian Smith

    31 EKİM 2006
  • Top10Series

    Top10Series

    26 Kasım 2008

İLGİLİ SORU / CEVAPLAR