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

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.

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.

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]

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

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

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

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.

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))

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))

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

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.

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

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

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)

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.

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

return [x for x in range(n+1) if n/x==int(n/x)]

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