Was ist der beste Weg, um alle Teiler einer Zahl zu erhalten?

Hier ist der sehr dumme Weg:

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

Das Ergebnis, das ich gerne hätte, ist ähnlich wie dieses, aber ich hätte gerne einen intelligenteren Algorithmus (dieser ist zu langsam und dumm :-)

Ich kann Primfaktoren und ihre Vielfalt schnell genug finden. Ich habe einen Generator, der auf diese Weise Faktoren erzeugt:

(Faktor1, Multiplizität1)
(Faktor2, Multiplizität2)
(Faktor3, Multiplizität3)
und so weiter ...

dh die Ausgabe von

for i in factorGenerator(100):
    print i

ist:

(2, 2)
(5, 2)

Ich weiß nicht, wie nützlich dies für das ist, was ich tun möchte (ich habe es für andere Probleme codiert), trotzdem möchte ich eine intelligentere Methode

for i in divisorGen(100):
    print i

Geben Sie Folgendes aus:

1
2
4
5
10
20
25
50
100

UPDATE: Vielen Dank an Greg Hewgill und seinen "intelligenten Weg" :) Das Berechnen aller Teiler von 100000000 dauerte 0,01 Sekunden mit seinem Weg gegen die 39er, die der dumme Weg auf meiner Maschine nahm, sehr cool: D.

UPDATE 2: Hör auf zu sagen, dass dies ein Duplikat dieses Beitrags ist. Um die Anzahl der Teiler einer bestimmten Zahl zu berechnen, müssen nicht alle Teiler berechnet werden. Es ist ein anderes Problem, wenn Sie denken, dass dies nicht der Fall ist, suchen Sie auf Wikipedia nach "Divisor-Funktion". Lesen Sie die Fragen und die Antwort vor dem Posten. Wenn Sie das Thema nicht verstehen, fügen Sie einfach keine nicht nützlichen und bereits gegebenen Antworten hinzu.

In Anbetracht Ihrer factorGeneratorFunktion divisorGensollte Folgendes funktionieren:

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

Die Gesamteffizienz dieses Algorithmus hängt vollständig von der Effizienz des Algorithmus ab factorGenerator.

Um das zu erweitern, was Shimi gesagt hat, sollten Sie Ihre Schleife nur von 1 bis zur Quadratwurzel von n ausführen. Um das Paar zu finden, tun Sie dies n / i, und dies deckt den gesamten Problembereich ab.

Wie bereits erwähnt, handelt es sich hierbei um ein NP- oder "schwieriges" Problem. Eine umfassende Suche, so wie Sie es tun, ist so gut wie es nur geht, um garantierte Antworten zu erhalten. Diese Tatsache wird von Verschlüsselungsalgorithmen und dergleichen verwendet, um sie zu sichern. Wenn jemand dieses Problem lösen würde, würde die meiste, wenn nicht die gesamte derzeitige "sichere" Kommunikation unsicher werden.

Python-Code:

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

Welches sollte eine Liste ausgeben wie:

[1, 2, 4, 5, 10, 20, 25, 50, 100]

Obwohl es dafür bereits viele Lösungen gibt, muss ich das wirklich posten :)

Dieser ist:

• lesbar
• kurz
• eigenständig, fertig zum Kopieren und Einfügen
• schnell (in Fällen mit vielen Primfaktoren und Teilern> 10-mal schneller als die akzeptierte Lösung)
• python3, python2 und pypy konform

Code:

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

Ich denke, Sie können math.sqrt(n)statt n / 2 anhalten .

Ich werde Ihnen ein Beispiel geben, damit Sie es leicht verstehen können. Jetzt sqrt(28)ist das 5.29so ceil(5.29)wird 6. Wenn ich also bei 6 aufhöre, kann ich alle Teiler bekommen. Wie?

Sehen Sie zuerst den Code und dann das Bild:

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

Siehe das Bild unten:

Nehmen wir an, ich habe bereits 1zu meiner Teilerliste hinzugefügt und beginne i=2damit

Am Ende aller Iterationen, wenn ich den Quotienten und den Divisor zu meiner Liste hinzugefügt habe, werden alle Divisoren von 28 gefüllt.

Quelle: So bestimmen Sie die Teiler einer Zahl

Ich mag Greg Lösung, aber ich wünschte, es wäre mehr Python. Ich denke, es wäre schneller und besser lesbar. Nach einiger Zeit des Codierens kam ich damit heraus.

Die ersten beiden Funktionen werden benötigt, um das kartesische Produkt aus Listen zu erstellen. Und kann wiederverwendet werden, wenn dieses Problem auftritt. Übrigens musste ich das selbst programmieren. Wenn jemand eine Standardlösung für dieses Problem kennt, kann er sich gerne an mich wenden.

"Factorgenerator" gibt jetzt ein Wörterbuch zurück. Und dann wird das Wörterbuch in "Teiler" eingespeist, die es verwenden, um zuerst eine Liste von Listen zu erzeugen, wobei jede Liste die Liste der Faktoren der Form p ^ n mit p prime ist. Dann machen wir das kartesische Produkt dieser Listen und verwenden schließlich Gregs Lösung, um den Divisor zu erzeugen. Wir sortieren sie und geben sie zurück.

Ich habe es getestet und es scheint etwas schneller zu sein als die vorherige Version. Ich habe es als Teil eines größeren Programms getestet, daher kann ich nicht wirklich sagen, wie viel es schneller ist.

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: Es ist das erste Mal, dass ich auf Stackoverflow poste. Ich freue mich auf Feedback.

Angepasst an CodeReview ist hier eine Variante, die funktioniert 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))

Hier ist eine intelligente und schnelle Möglichkeit, dies für Zahlen bis und um 10 ** 16 in reinem Python 3.6 zu tun.

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

Ich werde nur eine leicht überarbeitete Version von Anivarths (da ich glaube, dass es die pythonischste ist) als zukünftige Referenz hinzufügen.

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

Alte Frage, aber hier ist meine Meinung:

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

Sie können Proxy mit:

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

HINWEIS: Für Sprachen, die dies unterstützen, kann dies rekursiv sein.

Unter der Annahme, dass die factorsFunktion die Faktoren von n zurückgibt (z. B. factors(60)die Liste [2, 2, 3, 5]), ist hier eine Funktion zum Berechnen der Teiler von 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

Hier ist meine Lösung. Es scheint dumm zu sein, funktioniert aber gut ... und ich habe versucht, alle richtigen Teiler zu finden, also begann die Schleife bei 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

Wenn Sie sich nur für die Verwendung von Listenverständnissen interessieren und nichts anderes für Sie wichtig ist!

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)

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

Für mich funktioniert das gut und ist auch sauber (Python 3)

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

Nicht sehr schnell, gibt aber Teiler Zeile für Zeile zurück, wie Sie möchten. Sie können auch list.append (n) und list.append (number) ausführen, wenn Sie dies wirklich möchten