Was ist der effizienteste Weg zu finden, alle Faktoren einer Zahl in Python?
https://stackoverflow.com/questions/6800193
-
22-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Kann mir jemand erklären, einen effizienten Weg zu finden, alle Faktoren einer Zahl in Python (2.7)?
Ich kann erstellen Sie einen Algorithmus, um dies zu tun, aber ich denke, es ist schlecht codiert ist und zu lange dauert, um ein Ergebnis für eine große Anzahl.
Lösung
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)))
Dies wird alle Faktoren sehr schnell von einer Zahl zurückgeben n.
Warum Quadratwurzel als Obergrenze?
sqrt(x) * sqrt(x) = x. Wenn 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 geringer ist als oder gleich sqrt(x), Sie müssen also nur bis zu diesem Punkt suchen, um einen der beiden übereinstimmenden Faktoren zu finden. Sie können dann verwenden x / fac1 bekommen fac2.
Das reduce(list.__add__, ...) nimmt die kleinen Listen von [fac1, fac2] und zusammen mit ihnen in einer langen Liste anschließen.
Das [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 Gibt ein Paar Faktoren zurück, wenn der Rest beim Teilen n durch das kleinere ist null (es muss auch nicht das größere prüfen; es bekommt das nur durch Division n durch das kleinere.)
Das set(...) Außen wird Duplikate loswerden, was nur für perfekte Quadrate passiert. Zum n = 4, Dies wird zurückkehren 2 zweimal so set Werden einen von ihnen los.
Andere Tipps
Die von @AGF präsentierte Lösung ist großartig, aber man kann ~ 50% schneller Laufzeit für ein willkürliches seltsam Nummer durch Überprüfung auf Parität. 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 zu lösen Projekt Euler Rätselt mich. In einigen Problemen wird ein Divisor -Check innerhalb von zwei verschachtelten bezeichnet for Loops und die Leistung dieser Funktion ist daher wesentlich.
Wenn ich diese Tatsache mit der hervorragenden Lösung von AGF kombiniert habe, habe ich diese Funktion gelandet:
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 Overhead aus dieser Änderung jedoch länger dauern.
Ich habe einige Tests durchgeführt, um die Geschwindigkeit zu überprüfen. Unten ist der verwendete Code. Um die verschiedenen Diagramme zu produzieren, habe ich das verändert X = range(1,100,1) entsprechend.
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)
Kein signifikanter Unterschied hier, aber mit größeren Zahlen ist der Vorteil offensichtlich:
X = Bereich (1.100000,1000) (nur ungerade Zahlen)
X = Bereich (2.100000.100) (nur Zahlen)
X = Bereich (1.100000.1001) (Wechselparität)
AGFs Antwort ist wirklich ziemlich cool. Ich wollte sehen, ob ich es neu schreiben könnte, um es zu vermeiden reduce(). Das 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 Berechnen geplant:
start = 10000000
end = start + 40000
for n in range(start, end):
factors(n)
Ich habe es einmal geführt, um Python kompilieren zu lassen, dann lief es dreimal unter dem Befehl (1) und hielt die beste Zeit.
- Version reduzieren: 11,58 Sekunden
- ITERTOOLS -Version: 11.49 Sekunden
- Schwierige Version: 11.12 Sekunden
Beachten Sie, dass die ITertools -Version ein Tupel baut und an flacher_iter () weitergibt. Wenn ich den Code ändere, um stattdessen eine Liste zu erstellen, verlangsamt er sich geringfügig:
- Iterools (Liste) Version: 11,62 Sekunden
Ich glaube, dass die Version des schwierigen Generators in Python am schnellsten möglich ist. Aber es ist nicht viel schneller als die Reduzierung der Version, ungefähr 4% schneller, basierend auf meinen Messungen.
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
Ich habe die meisten dieser wundervollen Antworten mit Zeitleistung ausprobiert, um ihre Effizienz mit meiner einfachen Funktion zu vergleichen, und dennoch sehe ich ständig 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 es geschrieben ist, müssen Sie Mathematik importieren, um zu testen, aber das Ersetzen von Math.SQRT (n) durch N **. 5 sollte genauso gut funktionieren. Ich habe keine Zeit damit, Zeit für Duplikate zu prüfen, da Duplikate in einem Set unabhängig davon nicht existieren können.
Eine weitere Verbesserung afg & eryksun Lösung.Das folgende Stück code gibt eine sortierte Liste aller Faktoren, die ohne änderung der Laufzeit asymptotische Komplexität:
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 Liste.sort () - Funktion verwenden, um eine sortierte Liste gibt nlog(n) Komplexität;Es ist viel schneller zu verwenden, Liste.reverse() auf l2, die in O(n) Komplexität.(Das ist, wie python gemacht wird.) Nach l2.reverse(), l2 angehängt werden könnten, l1, um die sortierte Liste der Faktoren.
Beachten Sie, l1 enthält ich-s erhöhen.l2 enthält q-s, die rückläufig sind.Das ist der Grund hinter der Verwendung der oben genannten Idee.
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 lesbarer. Ich habe die Leistung dieses Ansatzes nicht getestet, aber asymptotisch sollte es gleich sein, und wenn die Leistung ein ernstes Problem ist, ist keine Lösung optimal.
Für n bis zu 10 ** 16 (vielleicht sogar ein bisschen mehr) ist 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))
In Sympy wird ein Algorithmus zur Branchenstärke genannt faktorint:
>>> 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 mit Methoden. Siehe die oben verlinkte Dokumentation.
Angesichts aller Primfaktoren können alle anderen Faktoren leicht gebaut werden.
Beachten Sie, dass selbst wenn die akzeptierte Antwort lange genug laufen durfte (dh eine Ewigkeit), um die oben genannte Zahl zu berücksichtigen, für einige große Zahlen fehlschlägt sie, das folgende Beispiel. Dies liegt an dem schlampigen int(n**0.5). Zum Beispiel wenn n = 10000000000000079**2, wir haben
>>> int(n**0.5)
10000000000000078L
Seit 10000000000000079 ist eine Prime, Der Algorithmus der akzeptierten Antwort wird diesen Faktor niemals finden. Beachten Sie, dass es nicht nur ein Off-by-One ist; Für größere Zahlen wird es um mehr ausgeschaltet. Aus diesem Grund ist es besser, Floating-Punkt-Zahlen in solchen Algorithmen zu vermeiden.
Hier ist eine andere Alternative ohne Reduzierung, die mit großen Zahlen gut funktioniert. Es verwendet sum Um die Liste zu fassen.
def factors(n):
return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
Stellen Sie sicher, dass Sie die Anzahl größer als größer als sqrt(number_to_factor) für ungewöhnliche Zahlen wie 99, die 3*3*11 und haben 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
Hier ist ein Beispiel, wenn Sie die Primes -Nummer verwenden möchten, um viel schneller zu werden. Diese Listen sind im Internet leicht zu finden. Ich habe Kommentare im Code hinzugefü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)]
Ein potenziell effizienterer Algorithmus als die hier bereits vorgestellten n). Der Trick hier ist zu Passen Sie die Grenze an Bis zu welcher Versuchsaufteilung wird jedes Mal benötigt, wenn Primat Faktoren 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 noch Testabteilung und nichts ausgefalleneres. und daher immer noch sehr begrenzt in seiner Effizienz (insbesondere für große Zahlen ohne kleine Divisoren).
Dies ist Python3; der Unternehmensbereich // Sollte das einzige sein, was Sie sich für Python 2 anpassen müssen (hinzufügen from __future__ import division).
Ihr maximaler Faktor ist nicht mehr als Ihre Nummer.
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á!
Die einfachste Art, Faktoren einer Zahl zu finden:
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
Verwendung set(...) macht den Code etwas langsamer und ist nur dann 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
Das if sq*sq != num: Bedingung ist für Zahlen wie 12 erforderlich, wobei die Quadratwurzel keine Ganzzahl ist, sondern der Boden der Quadratwurzel ein Faktor.
Beachten Sie, dass diese Version die Nummer selbst nicht zurückgibt, aber das ist eine einfache Lösung, wenn Sie sie möchten. Die Ausgabe ist auch nicht sortiert.
Ich habe es 10000 Mal auf allen Zahlen 1-200 und 100 Mal auf allen Nummern 1-5000 ausgeführt. Es übertrifft alle anderen Versionen, die ich getestet habe, darunter Dansalmos, Jason Schorns, Oxrocks, AGFs, Steveha und Eryksuns Lösungen, obwohl Oxrock's bei weitem am nächsten kommt.
Verwenden Sie etwas so Einfaches wie das folgende Listenverständnis und stellen fest, dass wir nicht testen müssen, und die Nummer, die wir finden möchten:
def factors(n):
return [x for x in range(2, n//2+1) if n%x == 0]
In Bezug auf die Verwendung von Quadratwurzel möchten wir Faktoren von 10. Der ganzzahlige Teil der finden sqrt(10) = 4 deshalb range(1, int(sqrt(10))) = [1, 2, 3, 4] und bis zu 4 Testen fehlt eindeutig 5.
Es sei denn, mir fehlt mir etwas vor, das ich vorschlagen würde, wenn Sie es so tun müssen, verwenden Sie es mit Verwendung int(ceil(sqrt(x))). Dies führt natürlich zu vielen unnötigen Aufrufen von Funktionen.
Ich denke, für Lesbarkeit und Geschwindigkeit @Oxrocks Lösung ist die beste. Hier ist der Code für Python 3+ umgeschrieben:
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
Ich war ziemlich überrascht, als ich diese Frage sah, dass niemand Numpy benutzte, selbst wenn Numpy ist viel schneller als Python Loops. Durch die Implementierung der Lösung von @agf mit numpy und es stellte sich im Durchschnitt heraus 8x schneller. Ich glaube, wenn Sie einige der anderen Lösungen in Numpy implementieren würden, könnten Sie erstaunliche Zeiten bekommen.
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 Zahlen der x-Achse nicht die Eingabe für die Funktionen sind. Die Eingabe in die Funktionen beträgt 2 bis die Zahl der x-Achse minus 1. Wob
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;
}
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.
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
