Jaki jest najbardziej skuteczny sposób znajdowania wszystkich czynników liczby w Pythonie?

Czy ktoś może mi wyjaśnić skuteczny sposób znajdowania wszystkich czynników liczby w Pythonie (2.7)?

Mogę stworzyć algorytm, który to zrobi, ale myślę, że jest on słabo zakodowany i uzyskanie wyniku dla dużej liczby zajmuje zbyt dużo czasu.

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

To bardzo szybko zwróci wszystkie czynniki danej liczby n.

Dlaczego pierwiastek kwadratowy jako górna granica?

sqrt(x) * sqrt(x) = x. Więc jeśli te dwa czynniki są takie same, to oba są pierwiastkiem kwadratowym. Jeśli zwiększysz jeden czynnik, musisz zmniejszyć drugi czynnik. Oznacza to, że jeden z dwóch zawsze będzie mniejszy lub równy sqrt(x), więc wystarczy przeszukać tylko do tego punktu, aby znaleźć jeden z dwóch dopasowanych czynników. Następnie możesz użyć, x / fac1aby uzyskać fac2.

To reduce(list.__add__, ...)zbieranie małych list [fac1, fac2]i łączenie ich w jedną długą listę.

Te [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0powroty parę czynników, jeśli pozostała po podzieleniu nprzez mniejszy jest zero (nie trzeba sprawdzić większy zbyt, to po prostu robi się to poprzez podzielenie nprzez mniejszy).

Na set(...)zewnątrz pozbywa się duplikatów, co dzieje się tylko w przypadku doskonałych kwadratów. Bo n = 4to powróci2 dwa razy, więc setpozbądź się jednego z nich.

Rozwiązanie przedstawione przez @agf jest świetne, ale można osiągnąć ~ 50% szybszy czas działania przy dowolnym dziwnym kursie liczby , sprawdzając parzystość. Ponieważ czynniki liczby nieparzystej zawsze są same w sobie nieparzyste, nie ma potrzeby sprawdzania ich w przypadku liczb nieparzystych.

Właśnie zacząłem samodzielnie rozwiązywać łamigłówki Projektu Euler . W niektórych przypadkach sprawdzanie dzielnika jest wywoływane w dwóch zagnieżdżonych forpętlach, a zatem wykonanie tej funkcji jest niezbędne.

Łącząc ten fakt z doskonałym rozwiązaniem agf, otrzymałem taką funkcję:

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

Jednak w przypadku małych liczb (~ <100) dodatkowe obciążenie wynikające z tej zmiany może spowodować, że funkcja będzie działać dłużej.

Wykonałem kilka testów, żeby sprawdzić prędkość. Poniżej znajduje się użyty kod. Aby utworzyć różne wykresy, odpowiednio zmieniłem X = range(1,100,1).

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 = zakres (1,100,1)

Nie ma tutaj znaczącej różnicy, ale przy większych liczbach przewaga jest oczywista:

X = zakres (1,100000,1000) (tylko liczby nieparzyste)

X = zakres (2,100000,100) (tylko liczby parzyste)

X = zakres (1,100000,1001) (zmienna parzystość)

odpowiedź agf jest naprawdę fajna. Chciałem zobaczyć, czy mogę go przepisać, aby uniknąć używania reduce(). Oto, co wymyśliłem:

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

Wypróbowałem także wersję, która wykorzystuje skomplikowane funkcje generatora:

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)

Zmierzyłem czas, obliczając:

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

Uruchomiłem go raz, aby Python mógł go skompilować, a następnie uruchomiłem go pod poleceniem time (1) trzy razy i zachowałem najlepszy czas.

• wersja zredukowana: 11,58 sekundy
• wersja itertools: 11,49 sekund
• trudna wersja: 11,12 sekundy

Zauważ, że wersja itertools buduje krotkę i przekazuje ją do flatten_iter (). Jeśli zmienię kod, aby zamiast tego zbudować listę, nieco zwalnia:

• iterools (lista) wersja: 11,62 sekundy

Uważam, że podstępna wersja funkcji generatora jest najszybsza z możliwych w Pythonie. Ale tak naprawdę nie jest dużo szybszy niż wersja zredukowana, około 4% szybciej na podstawie moich pomiarów.

Alternatywne podejście do odpowiedzi 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

Oto alternatywa dla rozwiązania @ agf, które implementuje ten sam algorytm w bardziej pythonowym stylu:

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

To rozwiązanie działa zarówno w Pythonie 2, jak i Pythonie 3 bez importu i jest znacznie bardziej czytelne. Nie testowałem wydajności tego podejścia, ale asymptotycznie powinno być tak samo, a jeśli wydajność jest poważnym problemem, żadne rozwiązanie nie jest optymalne.

W SymPy istnieje branżowy algorytm zwany 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}

Zajęło to mniej niż minutę. Przełącza się między mieszanką metod. Zobacz dokumentację, do której link znajduje się powyżej.

Biorąc pod uwagę wszystkie czynniki pierwsze, wszystkie inne czynniki można łatwo zbudować.

Zauważ, że nawet jeśli zaakceptowana odpowiedź mogła trwać wystarczająco długo (tj. Wieczność), aby uwzględnić powyższą liczbę, w przypadku niektórych dużych liczb zakończy się niepowodzeniem, jak w poniższym przykładzie. Wynika to z niechlujstwa int(n**0.5). Na przykład, kiedy n = 10000000000000079**2mamy

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

Ponieważ 10000000000000079 jest liczbą pierwszą , algorytm zaakceptowanej odpowiedzi nigdy nie znajdzie tego czynnika. Zwróć uwagę, że nie jest to tylko pojedynek; dla większych liczb będzie wyłączony o więcej. Z tego powodu lepiej unikać liczb zmiennoprzecinkowych w tego rodzaju algorytmach.

Dla n do 10 ** 16 (może nawet trochę więcej), oto szybkie, czyste rozwiązanie Pythona 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))

Dalsze ulepszenie rozwiązania afg i eryksun. Poniższy fragment kodu zwraca posortowaną listę wszystkich czynników bez zmiany asymptotycznej złożoności czasu wykonywania:

    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

Pomysł: Zamiast używać funkcji list.sort () do uzyskania posortowanej listy, która daje złożoność nlog (n); Znacznie szybciej jest używać list.reverse () na l2, co wymaga złożoności O (n). (Tak powstaje Python.) Po l2.reverse (), l2 może zostać dołączone do l1, aby otrzymać posortowaną listę czynników.

Zauważ, że l1 zawiera i -s, które rosną. l2 zawiera q -s, które maleją. To jest powód wykorzystania powyższej idei.

Wypróbowałem większość z tych wspaniałych odpowiedzi z czasem, aby porównać ich skuteczność z moją prostą funkcją, a jednak ciągle widzę, że moje wyniki przewyższają te wymienione tutaj. Pomyślałem, że podzielę się tym i zobaczę, co wszyscy myślicie.

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

Jak jest napisane, będziesz musiał zaimportować matematykę do testu, ale zastąpienie math.sqrt (n) przez n **. 5 powinno działać równie dobrze. Nie przejmuję się marnowaniem czasu na szukanie duplikatów, ponieważ duplikaty nie mogą istnieć w zestawie.

Oto kolejna alternatywa bez redukcji, która działa dobrze z dużymi liczbami. Używa sumdo spłaszczenia listy.

def factors(n):
    return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))

Pamiętaj, aby złapać liczbę większą niż w sqrt(number_to_factor)przypadku nietypowych liczb, takich jak 99, która ma 3 * 3 * 11 i 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

Najprostszy sposób na znalezienie czynników liczby:

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

Oto przykład, jeśli chcesz użyć liczb pierwszych, aby przejść znacznie szybciej. Listy te można łatwo znaleźć w Internecie. Dodałem komentarze w kodzie.

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

potencjalnie bardziej wydajny algorytm niż te już tutaj przedstawione (zwłaszcza jeśli są w nim małe fakty pierwsze n). sztuczka polega na dostosowaniu limitu , do którego wymagany jest podział próbny za każdym razem, gdy zostaną znalezione czynniki pierwsze:

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

jest to oczywiście nadal podział próbny i nic bardziej wyszukanego. a zatem nadal bardzo ograniczona jego wydajność (szczególnie w przypadku dużych liczb bez małych dzielników).

to jest python3; podział //powinien być jedyną rzeczą, którą musisz dostosować do Pythona 2 (dodaj from __future__ import division).

Użycie set(...)sprawia, że ​​kod jest nieco wolniejszy i jest naprawdę konieczne tylko wtedy, gdy sprawdzasz pierwiastek kwadratowy. Oto moja wersja:

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

if sq*sq != num:Warunkiem jest to konieczne do liczby, jak 12, przy czym pierwiastek nie jest liczbą całkowitą, a podłoga pierwiastka jest czynnikiem.

Zwróć uwagę, że ta wersja nie zwraca samego numeru, ale jest to łatwe rozwiązanie, jeśli chcesz. Dane wyjściowe również nie są sortowane.

Zmierzyłem czas 10000 razy na wszystkich numerach 1-200 i 100 razy na wszystkich numerach 1-5000. Przewyższa wszystkie inne testowane przeze mnie wersje, w tym rozwiązania dansalmo, Jasona Schorna, Oxrocka, agf, steveha i eryksun, choć zdecydowanie najbliższe jest rozwiązanie Oxrock.

Twój maksymalny współczynnik to nie więcej niż liczba, więc powiedzmy

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á!

 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. 

Użyj czegoś tak prostego, jak poniższa lista, zwracając uwagę, że nie musimy testować 1 i liczby, którą próbujemy znaleźć:

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

W odniesieniu do pierwiastka kwadratowego, powiedzmy, że chcemy znaleźć współczynniki 10. Część całkowita funkcji sqrt(10) = 4 powodu range(1, int(sqrt(10))) = [1, 2, 3, 4]i testowaniu do 4 wyraźnie brakuje 5.

Chyba że brakuje mi czegoś, co sugerowałbym, jeśli musisz to zrobić w ten sposób, używając int(ceil(sqrt(x))). Oczywiście powoduje to wiele niepotrzebnych wywołań funkcji.

Myślę, że dla czytelności i szybkości rozwiązanie @ oxrock jest najlepsze, więc oto kod przepisany dla Pythona 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

Byłem dość zaskoczony, gdy zobaczyłem to pytanie, że nikt nie używał numpy, nawet jeśli numpy jest znacznie szybszy niż pętle Pythona. Wdrażając rozwiązanie @ agf z numpy i okazało się średnio 8x szybciej . Wierzę, że gdybyś wdrożył niektóre inne rozwiązania w numpy, możesz uzyskać niesamowite czasy.

Oto moja funkcja:

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

Zauważ, że liczby na osi X nie są danymi wejściowymi dla funkcji. Dane wejściowe funkcji to 2 do liczby na osi x minus 1. Zatem gdzie dziesięć to wartość wejściowa to 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;
}

Myślę, że jest to najprostszy sposób:

    x = 23

    i = 1
    while i <= x:
      if x % i == 0:
        print("factor: %s"% i)
      i += 1