Was ist der effizienteste Weg, um alle Faktoren einer Zahl in Python zu finden?

144

Kann mir jemand erklären, wie man in Python (2.7) alle Faktoren einer Zahl effizient findet?

Ich kann einen Algorithmus erstellen, um dies zu tun, aber ich denke, er ist schlecht codiert und dauert zu lange, um ein Ergebnis für eine große Anzahl zu erzeugen.

Adnan
quelle
3
Ich kenne Python nicht. Aber diese Seite kann für Sie nützlich sein en.wikipedia.org/wiki/Integer_factorization
Stan
3
Wie wäre es mit primefac? pypi.python.org/pypi/primefac
Zubo

Antworten:

269
from functools import reduce

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

Dadurch werden alle Faktoren einer Zahl sehr schnell zurückgegeben n.

Warum Quadratwurzel als Obergrenze?

sqrt(x) * sqrt(x) = x. Wenn also die beiden Faktoren gleich sind, sind sie beide die Quadratwurzel. Wenn Sie einen Faktor größer machen, müssen Sie den anderen Faktor kleiner machen. Dies bedeutet, dass einer der beiden immer kleiner oder gleich ist sqrt(x), sodass Sie nur bis zu diesem Punkt suchen müssen, um einen der beiden übereinstimmenden Faktoren zu finden. Sie können dann verwenden x / fac1, um zu bekommen fac2.

Das reduce(list.__add__, ...)nimmt die kleinen Listen von [fac1, fac2]und fasst sie zu einer langen Liste zusammen.

Das [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0gibt ein Paar von Faktoren zurück, wenn der Rest, wenn Sie ndurch den kleineren dividieren, Null ist (es muss nicht auch der größere überprüft werden; dies wird nur durch Teilen ndurch den kleineren erreicht.)

Das set(...)Äußere beseitigt Duplikate, was nur bei perfekten Quadraten der Fall ist. Denn n = 4dies wird 2zweimal zurückkehren, also setwird einer von ihnen los.

agf
quelle
1
Ich habe dies aus einer Liste von Algorithmen auf meinem Computer kopiert. Alles, was ich getan habe, war, das zu kapseln sqrt- es ist wahrscheinlich, bevor die Leute wirklich darüber nachdachten, Python 3 zu unterstützen. Ich denke, die Site, von der ich es bekommen habe, hat es ausprobiert __iadd__und es war schneller . Ich scheine mich an etwas zu erinnern, x**0.5das schneller ist als sqrt(x)irgendwann - und auf diese Weise ist es kinderleichter.
Agf
8
Scheint 15% schneller zu sein, wenn ich if not n % ianstelle vonif n % i == 0
dansalmo
3
@sthzg Wir möchten, dass eine Ganzzahl und kein Gleitkommawert zurückgegeben wird. In Python 3 /wird ein Gleitkommawert zurückgegeben, auch wenn beide Argumente Ganzzahlen sind und genau teilbar sind, dh 4 / 2 == 2.0nicht2 .
Agf
7
Ich weiß, dass dies eine alte Frage ist, aber in Python 3.x müssen Sie hinzufügen from functools import reduce, damit dies funktioniert.
anonymoose
5
@unseen_rider: Das klingt nicht richtig. Können Sie etwas zur Sicherung bereitstellen?
Ry-
57

Die von @agf vorgestellte Lösung ist großartig, aber man kann eine ~ 50% schnellere Laufzeit für eine beliebige ungerade Zahl erreichen, indem man auf Parität prüft. Da die Faktoren einer ungeraden Zahl selbst immer ungerade sind, ist es nicht erforderlich, diese beim Umgang mit ungeraden Zahlen zu überprüfen.

Ich habe gerade angefangen, Project Euler- Rätsel selbst zu lösen . Bei einigen Problemen wird eine Divisorprüfung innerhalb von zwei verschachtelten forSchleifen aufgerufen , und die Leistung dieser Funktion ist daher wesentlich.

Wenn ich diese Tatsache mit der hervorragenden Lösung von agf kombiniere, habe ich folgende Funktion erhalten:

from math import sqrt
def factors(n):
        step = 2 if n%2 else 1
        return set(reduce(list.__add__,
                    ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

Bei kleinen Zahlen (~ <100) kann der zusätzliche Aufwand durch diese Änderung jedoch dazu führen, dass die Funktion länger dauert.

Ich habe einige Tests durchgeführt, um die Geschwindigkeit zu überprüfen. Unten ist der verwendete Code. Um die verschiedenen Handlungen zu erstellen, habe ich die X = range(1,100,1)entsprechend geändert .

import timeit
from math import sqrt
from matplotlib.pyplot import plot, legend, show

def factors_1(n):
    step = 2 if n%2 else 1
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n))+1, step) if n % i == 0)))

def factors_2(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0)))

X = range(1,100000,1000)
Y = []
for i in X:
    f_1 = timeit.timeit('factors_1({})'.format(i), setup='from __main__ import factors_1', number=10000)
    f_2 = timeit.timeit('factors_2({})'.format(i), setup='from __main__ import factors_2', number=10000)
    Y.append(f_1/f_2)
plot(X,Y, label='Running time with/without parity check')
legend()
show()

X = Bereich (1.100,1) X = Bereich (1.100,1)

Kein signifikanter Unterschied, aber bei größeren Zahlen liegt der Vorteil auf der Hand:

X = Bereich (1.100000.1000) (nur ungerade Zahlen) X = Bereich (1.100000.1000) (nur ungerade Zahlen)

X = Bereich (2.100000.100) (nur gerade Zahlen) X = Bereich (2.100000.100) (nur gerade Zahlen)

X = Bereich (1.100.000.1001) (alternierende Parität) X = Bereich (1.100.000.1001) (alternierende Parität)

Steinar Lima
quelle
29

Die Antwort von agf ist wirklich ziemlich cool. Ich wollte sehen, ob ich es umschreiben kann, um die Verwendung zu vermeiden reduce(). Folgendes habe ich mir ausgedacht:

import itertools
flatten_iter = itertools.chain.from_iterable
def factors(n):
    return set(flatten_iter((i, n//i) 
                for i in range(1, int(n**0.5)+1) if n % i == 0))

Ich habe auch eine Version ausprobiert, die knifflige Generatorfunktionen verwendet:

def factors(n):
    return set(x for tup in ([i, n//i] 
                for i in range(1, int(n**0.5)+1) if n % i == 0) for x in tup)

Ich habe es durch Rechnen zeitlich festgelegt:

start = 10000000
end = start + 40000
for n in range(start, end):
    factors(n)

Ich habe es einmal ausgeführt, damit Python es kompiliert, dann dreimal unter dem Befehl time (1) ausgeführt und die beste Zeit beibehalten.

  • Version reduzieren: 11,58 Sekunden
  • itertools-Version: 11,49 Sekunden
  • knifflige Version: 11,12 Sekunden

Beachten Sie, dass die itertools-Version ein Tupel erstellt und an flatten_iter () übergibt. Wenn ich den Code ändere, um stattdessen eine Liste zu erstellen, wird er etwas langsamer:

  • iterools (Liste) Version: 11,62 Sekunden

Ich glaube, dass die knifflige Version der Generatorfunktionen die schnellstmögliche in Python ist. Aber es ist nicht wirklich viel schneller als die reduzierte Version, ungefähr 4% schneller, basierend auf meinen Messungen.

steveha
quelle
2
Sie könnten die "knifflige Version" vereinfachen (unnötig entfernen for tup in):factors = lambda n: {f for i in range(1, int(n**0.5)+1) if n % i == 0 for f in [i, n//i]}
jfs
11

Ein alternativer Ansatz zur Antwort von agf:

def factors(n):    
    result = set()
    for i in range(1, int(n ** 0.5) + 1):
        div, mod = divmod(n, i)
        if mod == 0:
            result |= {i, div}
    return result
Eryk Sun.
quelle
1
Kannst du den div, mod Teil erklären?
Adnan
3
divmod (x, y) gibt ((xx% y) / y, x% y) zurück, dh den Quotienten und den Rest der Division.
c4757p
Dies behandelt doppelte Faktoren nicht gut - versuchen Sie es beispielsweise mit 81.
Phkahler
Ihre Antwort ist klarer, so dass ich sie gerade so weit bringen konnte, dass ich sie falsch verstehen konnte. Ich dachte an eine Primfaktorisierung, bei der Sie mehrere 3en aufrufen möchten. Dies sollte in Ordnung sein, da das OP darum gebeten hat.
Phkahler
Ich habe alles in einer Zeile zusammengefasst, weil Agfs Antwort dies tat. Ich war daran interessiert zu sehen, ob reduce()es wesentlich schneller war, also habe ich so ziemlich alles andere als den reduce()Teil genauso gemacht wie agf. Zur besseren Lesbarkeit wäre es schön, einen Funktionsaufruf wie is_even(n)und keinen Ausdruck wie zu sehen n % 2 == 0.
Steveha
10

Hier ist eine Alternative zu @ agfs Lösung, die denselben Algorithmus in einem pythonischeren Stil implementiert:

def factors(n):
    return set(
        factor for i in range(1, int(n**0.5) + 1) if n % i == 0
        for factor in (i, n//i)
    )

Diese Lösung funktioniert sowohl in Python 2 als auch in Python 3 ohne Importe und ist viel besser lesbar. Ich habe die Leistung dieses Ansatzes nicht getestet, aber asymptotisch sollte es dieselbe sein, und wenn die Leistung ein ernstes Problem darstellt, ist keine der beiden Lösungen optimal.

julianisch
quelle
9

Für n bis zu 10 ** 16 (vielleicht sogar ein bisschen mehr) gibt es hier eine schnelle, reine Python 3.6-Lösung:

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
quelle
8

In SymPy gibt es einen branchenüblichen Algorithmus namens factorint :

>>> from sympy import factorint
>>> factorint(2**70 + 3**80) 
{5: 2,
 41: 1,
 101: 1,
 181: 1,
 821: 1,
 1597: 1,
 5393: 1,
 27188665321L: 1,
 41030818561L: 1}

Dies dauerte weniger als eine Minute. Es wechselt zwischen einem Cocktail von Methoden. Siehe die oben verlinkte Dokumentation.

Angesichts aller Primfaktoren können alle anderen Faktoren leicht aufgebaut werden.


Beachten Sie, dass selbst wenn die akzeptierte Antwort lange genug (dh eine Ewigkeit) laufen gelassen wurde, um die obige Zahl zu berücksichtigen, sie bei einigen großen Zahlen fehlschlägt, wie im folgenden Beispiel. Das liegt an der Schlamperei int(n**0.5). Zum Beispiel, wenn n = 10000000000000079**2wir haben

>>> int(n**0.5)
10000000000000078L

Da 10000000000000079 eine Primzahl ist , wird der Algorithmus der akzeptierten Antwort diesen Faktor niemals finden. Beachten Sie, dass es nicht nur ein Einzelfall ist. für größere Zahlen wird es um mehr aus sein. Aus diesem Grund ist es besser, Gleitkommazahlen in Algorithmen dieser Art zu vermeiden.

Evgeni Sergeev
quelle
2
Es werden nicht alle Teiler gefunden, sondern nur Primfaktoren, daher ist es keine wirkliche Antwort. Sie sollten zeigen, wie alle anderen Faktoren aufgebaut werden können, und nicht nur sagen, dass es einfach ist! Übrigens könnten sympy.divisors besser zu dieser Frage passen.
Colin Pitrat
Beachten Sie auch, dass sympy.divisors nicht viel schneller ist als die akzeptierte Lösung.
Colin Pitrat
@ColinPitrat: Ich bezweifle, dass sympy.divisorsdas nicht viel schneller ist, insbesondere für Zahlen mit wenigen Teilern. Hast du Benchmarks?
Ry-
@ Ry Ich habe einen gemacht, als ich diesen Kommentar vor einem Jahr geschrieben habe. Das Schreiben eines Dokuments dauert 2 Minuten. Sie können es also noch einmal überprüfen.
Colin Pitrat
3
@ColinPitrat: Überprüft. Wie erwartet ist die akzeptierte Antwort ungefähr gleich schnell wie sympy.divisorsbei 100.000 und langsamer für alles, was höher ist (wenn Geschwindigkeit tatsächlich wichtig ist). (Und arbeitet natürlich sympy.divisorsmit Zahlen wie 10000000000000079**2.)
Ry-
6

Weitere Verbesserung der Lösung von afg & eryksun. Der folgende Code gibt eine sortierte Liste aller Faktoren zurück, ohne die asymptotische Komplexität der Laufzeit zu ändern:

    def factors(n):    
        l1, l2 = [], []
        for i in range(1, int(n ** 0.5) + 1):
            q,r = n//i, n%i     # Alter: divmod() fn can be used.
            if r == 0:
                l1.append(i) 
                l2.append(q)    # q's obtained are decreasing.
        if l1[-1] == l2[-1]:    # To avoid duplication of the possible factor sqrt(n)
            l1.pop()
        l2.reverse()
        return l1 + l2

Idee: Anstatt die Funktion list.sort () zu verwenden, um eine sortierte Liste zu erhalten, die die Komplexität von nlog (n) ergibt. Es ist viel schneller, list.reverse () auf l2 zu verwenden, was O (n) Komplexität erfordert. (So ​​wird Python erstellt.) Nach l2.reverse () kann l2 an l1 angehängt werden, um die sortierte Liste der Faktoren zu erhalten.

Beachten Sie, dass l1 i- s enthält, die zunehmen. l2 enthält q -s, die abnehmen. Das ist der Grund für die Verwendung der obigen Idee.

Pranjal Mittal
quelle
Ziemlich sicher list.reverseist O (n) nicht O (1), nicht dass es die Gesamtkomplexität verändert.
Agf
Ja, das ist richtig. Ich machte einen Fehler. Sollte O (n) sein. (Ich habe die Antwort jetzt auf die richtige aktualisiert)
Pranjal Mittal
Es ist ungefähr zweimal langsamer als die Lösungen von @ steveha oder @ agf.
JFS
Sie können eine kleine Geschwindigkeitsverbesserung (2-3%) feststellen, indem Sie zurückkehren l1 + l2.reversed()und die Liste nicht umkehren.
Rakurai
6

Ich habe die meisten dieser wunderbaren Antworten mit Zeit versucht, um ihre Effizienz mit meiner einfachen Funktion zu vergleichen, und dennoch sehe ich ständig, dass meine die hier aufgeführten übertreffen. Ich dachte, ich würde es teilen und sehen, was Sie alle denken.

def factors(n):
    results = set()
    for i in xrange(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            results.add(i)
            results.add(int(n/i))
    return results

Wie geschrieben, müssen Sie zum Testen Mathematik importieren, aber das Ersetzen von math.sqrt (n) durch n **. 5 sollte genauso gut funktionieren. Ich mache keine Zeit damit, nach Duplikaten zu suchen, da Duplikate in einem Satz trotzdem nicht existieren können.

Oxrock
quelle
Tolles Zeug! Wenn Sie int (math.sqrt (n)) + 1 außerhalb der for-Schleife setzen, sollten Sie etwas mehr Leistung daraus ziehen, da Sie es nicht bei jeder Iteration der for-Schleife neu berechnen müssen
Tristan Forward
3
@TristanForward: So funktionieren for-Schleifen in Python nicht. xrange(1, int(math.sqrt(n)) + 1)wird einmal ausgewertet.
Ry-
5

Hier ist eine weitere Alternative ohne Reduzierung, die bei großen Zahlen gut funktioniert. Es wird verwendet sum, um die Liste zu reduzieren.

def factors(n):
    return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
Dansalmo
quelle
1
Dies ist nicht der Fall, es ist unnötig quadratische Zeit. Verwenden sumoder reduce(list.__add__)reduzieren Sie eine Liste nicht.
juanpa.arrivillaga
5

Der einfachste Weg, Faktoren einer Zahl zu finden:

def factors(x):
    return [i for i in range(1,x+1) if x%i==0]
GooDeeJaY
quelle
4

Achten Sie darauf, die Nummer größer als sqrt(number_to_factor)bei ungewöhnlichen Zahlen wie 99 mit 3 * 3 * 11 und zu wählen floor sqrt(99)+1 == 10.

import math

def factor(x):
  if x == 0 or x == 1:
    return None
  res = []
  for i in range(2,int(math.floor(math.sqrt(x)+1))):
    while x % i == 0:
      x /= i
      res.append(i)
  if x != 1: # Unusual numbers
    res.append(x)
  return res
mbowden
quelle
1
Es werden nicht alle Faktoren einer Zahl erzeugt. Es berechnet Primfaktoren einer Zahl, zB für x=8erwartet : [1, 2, 4, 8], bekam:[2, 2, 2]
jfs
11 wird gefunden, wenn 9 in dem von @agf angegebenen Code enthalten ist. ʻI = 9 -> 99% 9 == 0 -> 9 und 99/9 = 11 wird hinzugefügt.
Steinar Lima
2

Hier ist ein Beispiel, wenn Sie die Primzahl verwenden möchten, um viel schneller zu gehen. Diese Listen sind im Internet leicht zu finden. Ich habe Kommentare in den Code eingefügt.

# http://primes.utm.edu/lists/small/10000.txt
# First 10000 primes

_PRIMES = (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
        31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
        73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 
        127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 
        179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 
        233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 
        283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 
        353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 
        419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 
        467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 
        547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 
        607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 
        661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 
        739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 
        811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 
        877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 
        947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 
# Mising a lot of primes for the purpose of the example
)


from bisect import bisect_left as _bisect_left
from math import sqrt as _sqrt


def get_factors(n):
    assert isinstance(n, int), "n must be an integer."
    assert n > 0, "n must be greather than zero."
    limit = pow(_PRIMES[-1], 2)
    assert n <= limit, "n is greather then the limit of {0}".format(limit)
    result = set((1, n))
    root = int(_sqrt(n))
    primes = [t for t in get_primes_smaller_than(root + 1) if not n % t]
    result.update(primes)  # Add all the primes factors less or equal to root square
    for t in primes:
        result.update(get_factors(n/t))  # Add all the factors associted for the primes by using the same process
    return sorted(result)


def get_primes_smaller_than(n):
    return _PRIMES[:_bisect_left(_PRIMES, n)]
Pierre Thibault
quelle
Ich habe ein Projekt auf Github erstellt: github.com/Pierre-Thibault/Factor .
Pierre Thibault
2

Ein potenziell effizienterer Algorithmus als die hier bereits vorgestellten (insbesondere wenn kleine Primfaktoren enthalten sind n). Der Trick dabei besteht darin, das Limit anzupassen, bis zu dem eine Testteilung erforderlich ist, wenn Primfaktoren gefunden werden:

def factors(n):
    '''
    return prime factors and multiplicity of n
    n = p0^e0 * p1^e1 * ... * pk^ek encoded as
    res = [(p0, e0), (p1, e1), ..., (pk, ek)]
    '''

    res = []

    # get rid of all the factors of 2 using bit shifts
    mult = 0
    while not n & 1:
        mult += 1
        n >>= 1
    if mult != 0:
        res.append((2, mult))

    limit = round(sqrt(n))
    test_prime = 3
    while test_prime <= limit:
        mult = 0
        while n % test_prime == 0:
            mult += 1
            n //= test_prime
        if mult != 0:
            res.append((test_prime, mult))
            if n == 1:              # only useful if ek >= 3 (ek: multiplicity
                break               # of the last prime) 
            limit = round(sqrt(n))  # adjust the limit
        test_prime += 2             # will often not be prime...
    if n != 1:
        res.append((n, 1))
    return res

Dies ist natürlich immer noch Probedivision und nichts Besonderes. und daher immer noch sehr begrenzt in seiner Effizienz (insbesondere für große Zahlen ohne kleine Teiler).

das ist python3; Die Division //sollte das einzige sein, was Sie für Python 2 anpassen müssen (hinzufügen from __future__ import division).

Hiro-Protagonist
quelle
1

Durch set(...)die Verwendung wird der Code etwas langsamer und ist nur dann wirklich erforderlich, wenn Sie die Quadratwurzel überprüfen. Hier ist meine Version:

def factors(num):
    if (num == 1 or num == 0):
        return []
    f = [1]
    sq = int(math.sqrt(num))
    for i in range(2, sq):
        if num % i == 0:
            f.append(i)
            f.append(num/i)
    if sq > 1 and num % sq == 0:
        f.append(sq)
        if sq*sq != num:
            f.append(num/sq)
    return f

Die if sq*sq != num:Bedingung ist für Zahlen wie 12 erforderlich, bei denen die Quadratwurzel keine ganze Zahl ist, aber der Boden der Quadratwurzel ein Faktor ist.

Beachten Sie, dass diese Version die Nummer selbst nicht zurückgibt, dies ist jedoch eine einfache Lösung, wenn Sie dies wünschen. Die Ausgabe ist auch nicht sortiert.

Ich habe es 10000 Mal für alle Nummern 1-200 und 100 Mal für alle Nummern 1-5000 ausgeführt. Es übertrifft alle anderen von mir getesteten Versionen, einschließlich der Lösungen von Dansalmo, Jason Schorn, Oxrock, Agf, Steveha und Eryksun, obwohl Oxrock bei weitem am nächsten kommt.

HamsterBoo
quelle
1

Ihr Maximalfaktor ist nicht mehr als Ihre Zahl. Nehmen wir also an

def factors(n):
    factors = []
    for i in range(1, n//2+1):
        if n % i == 0:
            factors.append (i)
    factors.append(n)

    return factors

voilá!

Polina Novikova
quelle
1
 import math

    '''
    I applied finding prime factorization to solve this. (Trial Division)
    It's not complicated
    '''


    def generate_factors(n):
        lower_bound_check = int(math.sqrt(n))  # determine lowest bound divisor range [16 = 4]
        factors = set()  # store factors
        for divisors in range(1, lower_bound_check + 1):  # loop [1 .. 4]
            if n % divisors == 0:
                factors.add(divisors)  # lower bound divisor is found 16 [ 1, 2, 4]
                factors.add(n // divisors)  # get upper divisor from lower [ 16 / 1 = 16, 16 / 2 = 8, 16 / 4 = 4]
        return factors  # [1, 2, 4, 8 16]


    print(generate_factors(12)) # {1, 2, 3, 4, 6, 12} -> pycharm output

 Pierre Vriens hopefully this makes more sense. this is an O(nlogn) solution. 
Tangang Atanga
quelle
0

Verwenden Sie etwas so Einfaches wie das folgende Listenverständnis, und beachten Sie, dass wir 1 und die Nummer, die wir finden möchten, nicht testen müssen:

def factors(n):
    return [x for x in range(2, n//2+1) if n%x == 0]

In Bezug auf die Verwendung der Quadratwurzel sagen wir, wir wollen Faktoren von 10 finden. Der ganzzahlige Teil von sqrt(10) = 4daher range(1, int(sqrt(10))) = [1, 2, 3, 4]und das Testen von bis zu 4 verfehlt eindeutig 5.

Sofern mir nichts fehlt, würde ich vorschlagen, wenn Sie es auf diese Weise tun müssen, mit int(ceil(sqrt(x))). Dies führt natürlich zu vielen unnötigen Funktionsaufrufen.

Jason Schorn
quelle
Das Problem bei dieser Lösung ist, dass sie viele Zahlen überprüft, die möglicherweise keine Faktoren sein können - und die höhere jedes Faktorpaars separat überprüft, wenn Sie bereits wissen, dass es sich um einen Faktor handelt, nachdem Sie die kleinere des Faktorpaars gefunden haben.
Agf
1
@JasonSchorn: Wenn Sie 2 finden, wissen Sie sofort, dass 10/2 = 5 auch ein Teiler ist, Sie müssen 5 nicht separat prüfen! :)
Moberg
0

Ich denke, für Lesbarkeit und Geschwindigkeit ist die Lösung von @ oxrock die beste. Hier ist der Code, der für Python 3+ neu geschrieben wurde:

def num_factors(n):
    results = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0: results.update([i,int(n/i)])
    return results
Nic Scozzaro
quelle
0

Ich war ziemlich überrascht, als ich diese Frage sah, dass niemand Numpy verwendete, selbst wenn Numpy viel schneller ist als Python-Loops. Durch die Implementierung der @ agf-Lösung mit numpy stellte sich heraus, dass sie durchschnittlich 8x schneller war . Ich glaube, wenn Sie einige der anderen Lösungen in Numpy implementieren, können Sie erstaunliche Zeiten erleben.

Hier ist meine Funktion:

import numpy as np
def b(n):
    r = np.arange(1, int(n ** 0.5) + 1)
    x = r[np.mod(n, r) == 0]
    return set(np.concatenate((x, n / x), axis=None))   

Beachten Sie, dass die Nummern der x-Achse nicht die Eingabe für die Funktionen sind. Die Eingabe für die Funktionen ist 2 für die Zahl auf der x-Achse minus 1. Wenn also zehn ist, wäre die Eingabe 2 ** 10-1 = 1023

Leistungstestergebnisse der Verwendung von numpy anstelle von for-Schleifen.

Benedikt Vilji Magnússon
quelle
1
Wenn Sie eine Bibliothek verwenden möchten, können Sie sie auch zur richtigen Bibliothek machen: SymPy, wie in der Antwort von Evgeni Sergeev zu sehen.
Ry-
0
import 'dart:math';
generateFactorsOfN(N){
  //determine lowest bound divisor range
  final lowerBoundCheck = sqrt(N).toInt();
  var factors = Set<int>(); //stores factors
  /**
   * Lets take 16:
   * 4 = sqrt(16)
   * start from 1 ...  4 inclusive
   * check mod 16 % 1 == 0?  set[1, (16 / 1)]
   * check mod 16 % 2 == 0?  set[1, (16 / 1) , 2 , (16 / 2)]
   * check mod 16 % 3 == 0?  set[1, (16 / 1) , 2 , (16 / 2)] -> unchanged
   * check mod 16 % 4 == 0?  set[1, (16 / 1) , 2 , (16 / 2), 4, (16 / 4)]
   *
   *  ******************* set is used to remove duplicate
   *  ******************* case 4 and (16 / 4) both equal to 4
   *  return factor set<int>.. this isn't ordered
   */

  for(var divisor = 1; divisor <= lowerBoundCheck; divisor++){
    if(N % divisor == 0){
      factors.add(divisor);
      factors.add(N ~/ divisor); // ~/ integer division 
    }
  }
  return factors;
}
Tangang Atanga
quelle
Fast alle Algorithmen beschränken sich hier auf den Bereich bis zur Zahl * .5, aber tatsächlich ist dieser Bereich viel kleiner. es ist tatsächlich sqrt der Zahl. Wenn wir den unteren Teiler haben, können wir den oberen leicht bekommen. da es nur die Zahl / der Teiler ist. für 16 bekomme ich 4 für das sqrt, dann schleife von 1 nach 4. da 2 ein unterer Teiler von 16 ist, nehmen wir 16/2, um 8 zu erhalten. Wenn wir 1 haben, dann ist 16 (16/1). Ich bin darauf gekommen, als ich etwas über Primfaktorisierung gelernt habe, daher weiß ich nicht, ob es woanders veröffentlicht wird, aber es funktioniert auch für große Zahlen. Ich kann eine Python-Lösung bereitstellen.
Tangang Atanga
-4

Ich denke, dies ist der einfachste Weg, dies zu tun:

    x = 23

    i = 1
    while i <= x:
      if x % i == 0:
        print("factor: %s"% i)
      i += 1
DeDude
quelle
Ihre Antwort liefert zwar das richtige Ergebnis, ist aber sehr ineffizient. Schauen Sie sich die akzeptierte Antwort an. Eine Erklärung, wie das Problem gelöst wird, hilft immer dabei, eine Antwort nützlicher zu machen.
Nick