Jaki jest najlepszy sposób na uzyskanie wszystkich dzielników liczby?

108

Oto bardzo głupi sposób:

def divisorGenerator(n):
    for i in xrange(1,n/2+1):
        if n%i == 0: yield i
    yield n

Wynik, który chciałbym uzyskać, jest podobny do tego, ale chciałbym mądrzejszego algorytmu (ten jest zbyt wolny i głupi :-)

Potrafię wystarczająco szybko znaleźć czynniki pierwsze i ich krotność. Mam generator, który generuje czynnik w ten sposób:

(współczynnik1, krotność1)
(współczynnik2, krotność2)
(współczynnik3, krotność3)
i tak dalej ...

czyli wyjście

for i in factorGenerator(100):
    print i

jest:

(2, 2)
(5, 2)

Nie wiem, na ile jest to przydatne w tym, co chcę robić (zakodowałem to pod kątem innych problemów), w każdym razie chciałbym mądrzejszego sposobu

for i in divisorGen(100):
    print i

wyślij to:

1
2
4
5
10
20
25
50
100

AKTUALIZACJA: Wielkie dzięki dla Grega Hewgilla i jego "sprytnego sposobu" :) Obliczenie wszystkich dzielników na 100000000 zajęło mu 0,01s wobec 39-tych, które głupi sposób objął moją maszynę, bardzo fajnie: D

UPDATE 2: Przestań mówić, że to duplikat tego postu. Obliczenie liczby dzielników podanej liczby nie wymaga obliczania wszystkich dzielników. To inny problem, jeśli myślisz, że tak nie jest, poszukaj opcji „Divisor function” na Wikipedii. Przeczytaj pytania i odpowiedź przed wysłaniem, jeśli nie rozumiesz, jaki jest temat, po prostu nie dodawaj nieprzydatnych i już udzielonych odpowiedzi.

Andrea Ambu
źródło
Powodem, dla którego zasugerowano, że to pytanie było prawie duplikatem „Algorytmu obliczania liczby dzielników danej liczby”, było to, że sugerowanym pierwszym krokiem w tym pytaniu było znalezienie wszystkich dzielników , co moim zdaniem jest dokładnie co próbowałeś zrobić?
Andrew Edgecombe,
4
Andrew, aby dowiedzieć się, ile jest dzielników, musisz po prostu znaleźć czynniki pierwsze, a następnie użyć ich do obliczenia, ile może być dzielników. W takim przypadku znajdowanie dzielników nie jest potrzebne.
Loïc Faure-Lacroix
1
@ Andrea Ambu, popraw nazwy funkcji
minerały

Odpowiedzi:

77

Biorąc pod uwagę twoją factorGeneratorfunkcję, oto divisorGenco powinno działać:

def divisorGen(n):
    factors = list(factorGenerator(n))
    nfactors = len(factors)
    f = [0] * nfactors
    while True:
        yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
        i = 0
        while True:
            f[i] += 1
            if f[i] <= factors[i][1]:
                break
            f[i] = 0
            i += 1
            if i >= nfactors:
                return

Ogólna wydajność tego algorytmu będzie zależeć całkowicie od wydajności factorGenerator.

Greg Hewgill
źródło
2
wow, obliczenie wszystkich dzielników wynoszących 100000000 zajęło 0,01 w porównaniu do 39, które przyjęły głupią drogę (zatrzymując się na n / 2). Bardzo fajnie, dziękuję!
Andrea Ambu
47
Dla tych z nas, którzy nie rozumieją Pythona, co to właściwie robi?
Matthew Scharley,
1
monoxide: oblicza wszystkie multiplikatywne kombinacje danych współczynników. Większość z nich powinna być oczywista; wiersz „yield” jest podobny do zwrotu, ale działa dalej po zwróceniu wartości. [0] * nfactors tworzy listę zer o długości nfactors. Redukcja (...) oblicza iloczyn czynników.
Greg Hewgill,
Notacja redukuj i lambda były tymi częściami, które w rzeczywistości były dla mnie zdezorientowane. Próbowałem zaimplementować algorytm, aby to zrobić w C #, używając funkcji rekurencyjnej, aby przejść przez tablicę czynników i pomnożyć je wszystkie razem, ale wydaje się, że ma okropną wydajność na liczbach takich jak 1024, które mają wiele czynników
Matthew Scharley
3
Jest to oczywiście znacznie lepsze niż dzielenie przez każdą liczbę do n / 2 lub nawet sqrt (n), ale ta konkretna implementacja ma dwie wady: całkiem nieskuteczne: tony mnożenia i potęgowania, wielokrotne mnożenie tych samych potęg itp. Wygląda Pythonic, ale nie sądzę, że w Pythonie chodzi o zabijanie wydajności. Problem drugi: dzielniki nie są zwracane w kolejności.
Tomasz Gandor
34

Aby rozwinąć to, co powiedział Shimi, powinieneś uruchamiać pętlę tylko od 1 do pierwiastka kwadratowego z n. Następnie, aby znaleźć parę, zrób n / i, a to obejmie całą przestrzeń problemu.

Jak również zauważono, jest to problem NP lub „trudny”. Wyczerpujące wyszukiwanie, sposób, w jaki to robisz, jest prawie tak dobre, jak to tylko możliwe, aby uzyskać gwarantowane odpowiedzi. Ten fakt jest wykorzystywany przez algorytmy szyfrowania i tym podobne, aby pomóc je zabezpieczyć. Gdyby ktoś miał rozwiązać ten problem, większość, jeśli nie cała nasza obecna „bezpieczna” komunikacja byłaby niepewna.

Kod Pythona:

import math

def divisorGenerator(n):
    large_divisors = []
    for i in xrange(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            yield i
            if i*i != n:
                large_divisors.append(n / i)
    for divisor in reversed(large_divisors):
        yield divisor

print list(divisorGenerator(100))

Który powinien wyświetlić listę taką jak:

[1, 2, 4, 5, 10, 20, 25, 50, 100]
Matthew Scharley
źródło
2
Ponieważ, gdy masz już listę elementów między 1..10, możesz wygenerować dowolny element między 11..100 trywialnie. Otrzymasz {1, 2, 4, 5, 10}. Podzielić 100 przez każdy z tych elementów i {100, 50, 20, 25, 10}.
Matthew Scharley
2
Na mocy definicji czynniki ZAWSZE generowane są w parach. Wyszukując tylko do sqrt (n), zmniejszasz swoją pracę o potęgę 2.
Matthew Scharley,
Jest bardzo szybszy niż wersja w moim poście, ale nadal jest zbyt wolny niż wersja wykorzystująca czynniki pierwsze
Andrea Ambu,
Zgadzam się, że to nie jest najlepsze rozwiązanie. Po prostu wskazałem „lepszy” sposób przeprowadzania „głupich” poszukiwań, który pozwoliłby zaoszczędzić sporo czasu.
Matthew Scharley,
Nie wykazano, że faktoryzacja jest NP-trudna. en.wikipedia.org/wiki/Integer_factorization Problem polegał na znalezieniu wszystkich dzielników, biorąc pod uwagę, że czynniki pierwsze (część trudna) zostały już znalezione.
Jamie,
19

Chociaż rozwiązań tego jest już wiele, naprawdę muszę to opublikować :)

Ten jest:

  • czytelny
  • krótki
  • samowystarczalny, gotowy do kopiowania i wklejania
  • szybki (w przypadkach z dużą ilością czynników pierwszych i dzielników,> 10 razy szybciej niż przyjęte rozwiązanie)
  • Zgodność z python3, python2 i pypy

Kod:

def divisors(n):
    # get factors and their counts
    factors = {}
    nn = n
    i = 2
    while i*i <= nn:
        while nn % i == 0:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 1

    primes = list(factors.keys())

    # generates factors from primes[k:] subset
    def generate(k):
        if k == len(primes):
            yield 1
        else:
            rest = generate(k+1)
            prime = primes[k]
            for factor in rest:
                prime_to_i = 1
                # prime_to_i iterates prime**i values, i being all possible exponents
                for _ in range(factors[prime] + 1):
                    yield factor * prime_to_i
                    prime_to_i *= prime

    # in python3, `yield from generate(0)` would also work
    for factor in generate(0):
        yield factor
Tomas Kulich
źródło
Chciałbym zastąpić while i*i <= nnprzez while i <= limit, gdzielimit = math.sqrt(n)
Rafa0809
17

Myślę, że możesz się zatrzymać math.sqrt(n)zamiast n / 2.

Podam ci przykład, abyś mógł to łatwo zrozumieć. Teraz sqrt(28)jest 5.29tak ceil(5.29)będzie 6. Więc jeśli zatrzymam się na 6, to otrzymam wszystkie dzielniki. W jaki sposób?

Najpierw zobacz kod, a następnie zobacz obrazek:

import math
def divisors(n):
    divs = [1]
    for i in xrange(2,int(math.sqrt(n))+1):
        if n%i == 0:
            divs.extend([i,n/i])
    divs.extend([n])
    return list(set(divs))

Teraz zobacz poniższy obrazek:

Powiedzmy, że dodałem już 1do mojej listy dzielników i zacznę od i=2tak

Dzielniki 28

Tak więc pod koniec wszystkich iteracji, gdy dodałem iloraz i dzielnik do mojej listy, wypełnione są wszystkie dzielniki 28.

Źródło: jak określić dzielniki liczby

Anivarth
źródło
2
Ładnie ładnie!! math.sqrt(n) instead of n/2jest obowiązkowy dla elegancji
Rafa0809
To jest niepoprawne. Zapomniałeś, że n jest podzielne przez siebie.
jasonleonhard
1
Niezła odpowiedź. Proste i przejrzyste. Ale dla Pythona 3 są 2 niezbędne zmiany: n / i powinno być wpisane przy użyciu int (n / i), ponieważ n / i daje liczbę zmiennoprzecinkową. Również rangex jest przestarzały w Pythonie 3 i został zastąpiony zakresem.
Geoffroy CALA
7

Podoba mi się rozwiązanie Grega, ale chciałbym, żeby było bardziej podobne do Pythona. Wydaje mi się, że byłoby to szybsze i bardziej czytelne; więc po pewnym czasie kodowania wyszedłem z tego.

Dwie pierwsze funkcje są potrzebne do stworzenia iloczynu kartezjańskiego list. I może być ponownie użyty, gdy tylko pojawi się ten problem. Swoją drogą sam musiałem to zaprogramować, jeśli ktoś zna standardowe rozwiązanie tego problemu to zapraszam do kontaktu.

„Factorgenerator” zwraca teraz słownik. Następnie słownik jest wprowadzany do „dzielników”, którzy używają go do generowania najpierw listy list, gdzie każda lista jest listą czynników postaci p ^ n z p liczbą pierwszą. Następnie tworzymy iloczyn kartezjański tych list i na koniec używamy rozwiązania Grega do wygenerowania dzielnika. Sortujemy je i zwracamy.

Przetestowałem go i wydaje się, że jest nieco szybszy niż poprzednia wersja. Przetestowałem go jako część większego programu, więc nie mogę powiedzieć, o ile jest szybszy.

Pietro Speroni (pietrosperoni dot it)

from math import sqrt


##############################################################
### cartesian product of lists ##################################
##############################################################

def appendEs2Sequences(sequences,es):
    result=[]
    if not sequences:
        for e in es:
            result.append([e])
    else:
        for e in es:
            result+=[seq+[e] for seq in sequences]
    return result


def cartesianproduct(lists):
    """
    given a list of lists,
    returns all the possible combinations taking one element from each list
    The list does not have to be of equal length
    """
    return reduce(appendEs2Sequences,lists,[])

##############################################################
### prime factors of a natural ##################################
##############################################################

def primefactors(n):
    '''lists prime factors, from greatest to smallest'''  
    i = 2
    while i<=sqrt(n):
        if n%i==0:
            l = primefactors(n/i)
            l.append(i)
            return l
        i+=1
    return [n]      # n is prime


##############################################################
### factorization of a natural ##################################
##############################################################

def factorGenerator(n):
    p = primefactors(n)
    factors={}
    for p1 in p:
        try:
            factors[p1]+=1
        except KeyError:
            factors[p1]=1
    return factors

def divisors(n):
    factors = factorGenerator(n)
    divisors=[]
    listexponents=[map(lambda x:k**x,range(0,factors[k]+1)) for k in factors.keys()]
    listfactors=cartesianproduct(listexponents)
    for f in listfactors:
        divisors.append(reduce(lambda x, y: x*y, f, 1))
    divisors.sort()
    return divisors



print divisors(60668796879)

PS Po raz pierwszy wysyłam post do stackoverflow. Z niecierpliwością czekam na wszelkie uwagi.

Pietro Speroni
źródło
W Pythonie 2.6 jest itertools.product ().
jfs
Wersja, która wszędzie używa generatorów zamiast list.append, może być czystsza.
jfs
Sito Eratostenesa można wykorzystać do generowania liczb pierwszych mniejszych lub równych sqrt (n) stackoverflow.com/questions/188425/project-euler-problem#193605
jfs
1
Styl kodowania: wykładniki = [k ** x dla k, v we współczynnikach.items () dla x w zakresie (v + 1)]
jfs
Dla listexponents: [[k ** x for x in range (v + 1)] for k, v inactors.items ()]
klenwell
3

Oto sprytny i szybki sposób na zrobienie tego dla liczb do i około 10 ** 16 w czystym Pythonie 3.6,

from itertools import compress

def primes(n):
    """ Returns  a list of primes < n for n > 2 """
    sieve = bytearray([True]) * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = bytearray((n-i*i-1)//(2*i)+1)
    return [2,*compress(range(3,n,2), sieve[1:])]

def factorization(n):
    """ Returns a list of the prime factorization of n """
    pf = []
    for p in primeslist:
      if p*p > n : break
      count = 0
      while not n % p:
        n //= p
        count += 1
      if count > 0: pf.append((p, count))
    if n > 1: pf.append((n, 1))
    return pf

def divisors(n):
    """ Returns an unsorted list of the divisors of n """
    divs = [1]
    for p, e in factorization(n):
        divs += [x*p**k for k in range(1,e+1) for x in divs]
    return divs

n = 600851475143
primeslist = primes(int(n**0.5)+1) 
print(divisors(n))
Bruno Astrolino
źródło
Jak nazywa się algorytm używany do znajdowania liczb pierwszych i rozkładania na czynniki? Ponieważ chcę to zaimplementować w C # ..
Kyu96
2

Zaadaptowano z CodeReview , oto wariant, który działa num=1!

from itertools import product
import operator

def prod(ls):
   return reduce(operator.mul, ls, 1)

def powered(factors, powers):
   return prod(f**p for (f,p) in zip(factors, powers))


def divisors(num) :

   pf = dict(prime_factors(num))
   primes = pf.keys()
   #For each prime, possible exponents
   exponents = [range(i+1) for i in pf.values()]
   return (powered(primes,es) for es in product(*exponents))
YvesgereY
źródło
1
I wydają się być uzyskiwanie błąd: NameError: global name 'prime_factors' is not defined. Żadna z pozostałych odpowiedzi ani pierwotne pytanie nie określa, co to robi.
AnnanFay
2

Dodam tylko nieco poprawioną wersję Anivartha (ponieważ uważam, że jest najbardziej pytoniczna) do wykorzystania w przyszłości.

from math import sqrt

def divisors(n):
    divs = {1,n}
    for i in range(2,int(sqrt(n))+1):
        if n%i == 0:
            divs.update((i,n//i))
    return divs
ppw0
źródło
1

Stare pytanie, ale oto moje podejście:

def divs(n, m):
    if m == 1: return [1]
    if n % m == 0: return [m] + divs(n, m - 1)
    return divs(n, m - 1)

Możesz proxy za pomocą:

def divisorGenerator(n):
    for x in reversed(divs(n, n)):
        yield x

UWAGA: W przypadku języków, które obsługują, może to być rekurencyjne.

joksnet
źródło
0

Zakładając, że factorsfunkcja zwraca czynniki n (na przykład factors(60)zwraca listę [2, 2, 3, 5]), oto funkcja obliczająca dzielniki n :

function divisors(n)
    divs := [1]
    for fact in factors(n)
        temp := []
        for div in divs
            if fact * div not in divs
                append fact * div to temp
        divs := divs + temp
    return divs
user448810
źródło
Czy to Python? W każdym razie na pewno nie jest to Python 3.x.
GinKin
To pseudokod, który powinien być łatwy do przetłumaczenia na Pythona.
user448810
3 lata później, lepiej późno niż wcale :) IMO, to najprostszy, najkrótszy kod, który to robi. Nie mam tabeli porównawczej, ale mogę rozkładać na czynniki i obliczać dzielniki nawet do miliona w 1s na moim przenośnym laptopie i5.
Riyaz Mansoor
0

Oto moje rozwiązanie. Wydaje się, że to głupie, ale działa dobrze ... i próbowałem znaleźć wszystkie właściwe dzielniki, więc pętla zaczęła się od i = 2.

import math as m 

def findfac(n):
    faclist = [1]
    for i in range(2, int(m.sqrt(n) + 2)):
        if n%i == 0:
            if i not in faclist:
                faclist.append(i)
                if n/i not in faclist:
                    faclist.append(n/i)
    return facts
Amber Xue
źródło
typo: return fact => return faclist
Jonath P
0

Jeśli zależy Ci tylko na używaniu list składanych i nic innego nie ma dla Ciebie znaczenia!

from itertools import combinations
from functools import reduce

def get_devisors(n):
    f = [f for f,e in list(factorGenerator(n)) for i in range(e)]
    fc = [x for l in range(len(f)+1) for x in combinations(f, l)]
    devisors = [1 if c==() else reduce((lambda x, y: x * y), c) for c in set(fc)]
    return sorted(devisors)
Sadiq
źródło
0

Jeśli twój komputer ma mnóstwo pamięci, brutalna pojedyncza linia może być wystarczająco szybka dzięki numpy:

N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out: 
array([      1,       2,       4,       5,       8,      10,      16,
            20,      25,      32,      40,      50,      64,      80,
           100,     125,     128,     160,     200,     250,     320,
           400,     500,     625,     640,     800,    1000,    1250,
          1600,    2000,    2500,    3125,    3200,    4000,    5000,
          6250,    8000,   10000,   12500,   15625,   16000,   20000,
         25000,   31250,   40000,   50000,   62500,   78125,   80000,
        100000,  125000,  156250,  200000,  250000,  312500,  400000,
        500000,  625000, 1000000, 1250000, 2000000, 2500000, 5000000])

Zajmuje mniej niż 1s na moim wolnym komputerze.

Mathieu Villion
źródło
0

Moje rozwiązanie za pomocą funkcji generatora to:

def divisor(num):
    for x in range(1, num + 1):
        if num % x == 0:
            yield x
    while True:
        yield None
Eugene
źródło
-1
return [x for x in range(n+1) if n/x==int(n/x)]
user3697453
źródło
3
Pytający poprosił o lepszy algorytm, a nie tylko ładniejszy format.
Veedrac
4
Musisz użyć zakresu (1, n + 1), aby uniknąć dzielenia przez zero. Ponadto musisz użyć float (n) dla pierwszego dzielenia, jeśli używasz Pythona 2.7, tutaj 1/2 = 0
Jens Munk
-1

U mnie to działa dobrze i jest również czyste (Python 3)

def divisors(number):
    n = 1
    while(n<number):
        if(number%n==0):
            print(n)
        else:
            pass
        n += 1
    print(number)

Niezbyt szybko, ale zwraca dzielniki linia po linii tak, jak chciałeś, możesz także zrobić list.append (n) i list.append (liczba), jeśli naprawdę chcesz

tomekch6
źródło