Qual è il modo più efficiente di trovare tutti i fattori di un numero in Python?
https://stackoverflow.com/questions/6800193
-
22-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Can qualcuno mi spieghi un modo efficiente di trovare tutti i fattori di un numero in Python (2.7)?
I in grado di creare un algoritmo per fare questo, ma penso che è scarsamente codificato e impiega troppo tempo per produrre un risultato per un gran numero.
Soluzione
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)))
Ciò restituirà tutti i fattori, molto rapidamente, di un certo numero n.
Perché radice quadrata come limite superiore?
sqrt(x) * sqrt(x) = x. Quindi, se i due fattori sono gli stessi, sono entrambi la radice quadrata. Se si effettua un fattore più grande, si deve fare l'altro fattore più piccolo. Ciò significa che uno dei due sarà sempre inferiore o uguale a sqrt(x), quindi bisogna cercare fino a quel punto per trovare uno dei due fattori di corrispondenza solo. È quindi possibile utilizzare x / fac1 per ottenere fac2.
Il reduce(list.__add__, ...) sta prendendo le piccole liste di [fac1, fac2] e li unisce insieme in una lunga lista.
Il [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0 restituisce un paio di fattori, se il resto quando si divide n dal più piccolo è pari a zero (non ha bisogno di controllare il più grande troppo, ma ottiene solo che dividendo n da quello più piccolo.)
Il set(...) sulla parte esterna è sbarazzarsi di duplicati, che avviene solo per i quadrati perfetti. Per n = 4, questo tornerà 2 due volte, in modo da set si libera di uno di loro.
Altri suggerimenti
La soluzione presentata da @agf è grande, ma si può raggiungere ~ 50% più veloce tempo di correre per un arbitrario dispari il numero controllando per la parità. Per quanto i fattori di un numero dispari sono sempre dispari se stessi, non è necessario controllare questi quando si tratta di numeri dispari.
Ho appena iniziato a risolvere i Project Euler puzzle di me stesso. In alcuni problemi, un controllo divisore è chiamato all'interno di due cicli annidati for, e le prestazioni di questa funzione è quindi essenziale.
La combinazione di questo fatto con un eccellente soluzione di AGF, ho finito con questa funzione:
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)))
Tuttavia, su piccoli numeri (~ <100), il sovraccarico da questa alterazione può causare la funzione per richiedere più tempo.
Ho eseguito alcuni test per verificare la velocità. Di seguito è riportato il codice utilizzato. Per produrre le diverse trame, ho alterato il X = range(1,100,1) di conseguenza.
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 = gamma (1,100,1)
Nessuna significativa differenza qui, ma con numeri più grandi, il vantaggio è evidente:
X = gamma (1,100000,1000) (solo i numeri dispari)
X = gamma (2,100000,100) (solo numeri pari)
X = gamma (1,100000,1001) (parità alternata)
di AGF è davvero piuttosto fresco. Volevo vedere se riuscivo a riscrivere per evitare di utilizzare reduce(). Questo è ciò che mi si avvicinò con:
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))
Ho provato anche una versione che utilizza funzioni di generatore difficili:
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)
ho cronometrato calcolando:
start = 10000000
end = start + 40000
for n in range(start, end):
factors(n)
Ho eseguito una volta a lasciare Python compilarlo, poi corse sotto il tempo (1) di comando per tre volte e ho continuato il momento migliore.
- ridurre versione: 11.58 secondi
- itertools versione: 11.49 secondi
- Versione difficile: 11.12 secondi
Si noti che la versione itertools sta costruendo una tupla e passarlo a flatten_iter (). Se cambio il codice per costruire una lista, invece, rallenta un po ':
- iterools (elenco) Versione: 11.62 secondi
Credo che la delicata versione funzioni del generatore è il più veloce possibile in Python. Ma non è in realtà molto più veloce rispetto alla versione a ridurre, circa il 4% più veloce sulla base delle mie misure.
Un approccio alternativo alla risposta di 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
Ho provato la maggior parte di queste meravigliose risposte con timeit per confrontare la loro efficienza contro la mia funzione semplice, eppure ho sempre vedere il mio sovraperformare quelli elencati qui. Ho pensato di condividere e vedere cosa ne pensate.
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
Come è scritto si dovrà importare matematica per prova, ma sostituendo Math.sqrt (n) con n **. 5 dovrebbe funzionare altrettanto bene. Non mi preoccupo di perdere il controllo del tempo per i duplicati, perché non possono esistere duplicati in un set a prescindere.
Un ulteriore miglioramento di AFG & soluzione eryksun. Il seguente pezzo di codice restituisce un elenco ordinato di tutti i fattori senza cambiare fase di esecuzione complessità asintotica:
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
Idea: Invece di utilizzare la funzione di list.sort () per ottenere un elenco ordinato che dà nlog (n) la complessità; E 'molto più veloce per uso list.reverse () su L2 che prende O (n) la complessità. (Ecco come pitone è fatto.) Dopo l2.reverse (), L2 può essere aggiunto a l1 per ottenere l'elenco ordinato di fattori.
Si noti, l1 contiene -s che stanno aumentando. l2 contiene q -s tendenzialmente in diminuzione. Questo è il motivo dietro utilizzando l'idea di cui sopra.
Ecco un'alternativa a @ di AGF soluzione che implementa lo stesso algoritmo in uno stile più divinatorio:
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)
)
Questa soluzione funziona sia in Python 2 e Python 3 con importazioni ed è molto più leggibile. Non ho ancora testato le prestazioni di questo approccio, ma asintoticamente Dovrebbe essere lo stesso, e se le prestazioni sono un problema serio, né la soluzione è ottimale.
per n fino a 10 ** 16 (forse anche un po 'di più), ecco un veloce pura soluzione di Python 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))
C'è un algoritmo industria-resistenza in SymPy chiamato 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}
Questo ha preso meno di un minuto. Si passa tra un cocktail di metodi. Vedere la documentazione legata sopra.
In considerazione tutti i fattori primi, tutti gli altri fattori può essere costruito facilmente.
Si noti che, anche se la risposta accettata è stato permesso di correre per un tempo sufficiente (cioè un'eternità) al fattore il numero di cui sopra, per alcuni grandi numeri fallirà, come nel seguente esempio. Ciò è dovuto al int(n**0.5) sciatta. Per esempio, quando n = 10000000000000079**2, abbiamo
>>> int(n**0.5)
10000000000000078L
10000000000000079 è un numero primo , l'algoritmo di risposta accettata non potrà mai trovare questo fattore. Si noti che non è solo un off-by-one; per i numeri più grandi, sarà fuori da più. Per questo motivo è meglio evitare numeri a virgola mobile in algoritmi di questo tipo.
Ecco un altro alternativo, senza ridurre tale si comporta bene con i grandi numeri. Esso utilizza sum per appiattire la lista.
def factors(n):
return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
Essere sicuri di prendere il numero più grande di sqrt(number_to_factor) per i numeri insoliti come il 99 che ha 3 * 3 * 11 e 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
Ecco un esempio, se si desidera utilizzare il numero di numeri primi di andare molto più veloce. Queste liste sono facili da trovare su internet. Ho aggiunto i commenti nel codice.
# 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)]
un algoritmo potenzialmente più efficienti di quelli presentati qui già (soprattutto se ci sono piccoli factons prime in n). il trucco è quello di regolare il limite fino a cui è necessario divisione di prova ogni volta fattori primi si trovano:
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
questo è di divisione ovviamente ancora prova e niente di più fantasia. e quindi ancora molto limitata nella sua efficacia (in particolare per i grandi numeri senza piccoli divisori).
questo è python3; il // divisione dovrebbe essere l'unica cosa che serve per adattare per Python 2 (add from __future__ import division).
il vostro fattore di massima, non è più di quanto il tuo numero, così, diciamo
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à!
Il modo più semplice di trovare fattori di un numero:
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
Utilizzando set(...) rende il codice leggermente più lento, ed è veramente solo necessario quando si controlla la radice quadrata. Ecco la mia versione:
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
La condizione if sq*sq != num: è necessaria per numeri come 12, dove la radice quadrata non è un intero, ma il pavimento della radice quadrata è un fattore.
Si noti che questa versione non restituisce il numero stesso, ma che è una soluzione semplice se lo si desidera. L'uscita, inoltre, non è ordinato.
ho cronometrato in esecuzione 10000 volte su tutti i numeri 1-200 e 100 volte su tutti i numeri 1-5000. Si supera tutte le altre versioni che ho provato, tra cui dansalmo di Jason, Schorn di, oxrock di AGF, di, steveha di, e le soluzioni di eryksun, anche se oxrock è di gran lunga la più vicina.
Usa qualcosa di semplice come la seguente lista di comprensione, notando che non abbiamo bisogno di test 1 e il numero che stanno cercando di trovare:
def factors(n):
return [x for x in range(2, n//2+1) if n%x == 0]
In riferimento all'uso di radice quadrata, diciamo vogliamo trovare fattori di 10. La parte intera del sqrt(10) = 4 quindi range(1, int(sqrt(10))) = [1, 2, 3, 4] e prova fino a 4 chiaramente non trova 5.
A meno che non mi manca qualcosa vorrei suggerire, se si deve fare in questo modo, utilizzando int(ceil(sqrt(x))). Naturalmente questo produce un sacco di chiamate inutili alle funzioni.
Credo che per migliorare la leggibilità e la velocità @ soluzione oxrock è la migliore, ecco il codice riscritto per Python 3 +:
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
Sono rimasto piuttosto sorpreso quando ho visto questa domanda che nessuno NumPy utilizzata anche quando NumPy è modo più veloce di loop Python. Implementando @ soluzione di AGF con NumPy e si è scoperto in media 8x più veloce . I belive che se implementato alcune delle altre soluzioni in NumPy si potrebbe ottenere volte sorprendenti.
Questa è la mia funzione:
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))
Si noti che i numeri delle ascisse non sono l'input per le funzioni. L'ingresso alle funzioni è 2 il numero sul ascisse meno 1. Allora, dove dieci è l'ingresso sarebbe 2 ** 10-1 = 1023
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.
Mi sa che questo è il modo più semplice per farlo:
x = 23
i = 1
while i <= x:
if x % i == 0:
print("factor: %s"% i)
i += 1
