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


142

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.


3
Nie znam Pythona. Ale ta strona może ci się przydać en.wikipedia.org/wiki/Integer_factorization
Stan

3
A co powiesz na używanie primefac? pypi.python.org/pypi/primefac
Zubo

Odpowiedzi:


265
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.


1
Skopiowałem i wkleiłem to z listy algorytmów na moim komputerze, wszystko co zrobiłem to hermetyzacja sqrt- to prawdopodobnie zanim ludzie naprawdę myśleli o wsparciu Pythona 3. Myślę, że strona, z której ją otrzymałem, wypróbowała to __iadd__i była szybsza . Wydaje mi się, że coś pamiętam o x**0.5byciu szybszym niż sqrt(x)w pewnym momencie - i dzięki temu jest to bardziej niezawodne.
agf

7
Wydaje się, że działa 15% szybciej, jeśli if not n % iif n % i == 0
użyję

3
@sthzg Chcemy, aby zwracał liczbę całkowitą, a nie liczbę zmiennoprzecinkową, a w Pythonie 3 /zwróci wartość zmiennoprzecinkową, nawet jeśli oba argumenty są liczbami całkowitymi i są one dokładnie podzielne, tj . 4 / 2 == 2.0nie 2.
agf

7
Wiem, że to stare pytanie, ale w Pythonie 3.x musisz dodać, from functools import reduceaby to zadziałało.
anonymoose

5
@unseen_rider: To nie brzmi dobrze. Czy możesz podać cokolwiek, aby to potwierdzić?
Ry-

55

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) 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 (1,100000,1000) (tylko liczby nieparzyste)

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

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


28

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.


2
możesz uprościć „podstępną wersję” (usunąć niepotrzebne 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

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

1
Czy możesz wyjaśnić część div, mod?
Adnan

3
divmod (x, y) zwraca ((xx% y) / y, x% y), tj. iloraz i pozostałą część dzielenia.
c4757p

To nie radzi sobie dobrze z powielonymi czynnikami - na przykład spróbuj 81.
phkahler

Twoja odpowiedź jest jaśniejsza, więc byłem w stanie ją zrozumieć na tyle, by źle zrozumieć. Myślałem o rozkładzie na czynniki pierwsze, w którym chciałbyś wywołać wiele trójek. Powinno to wystarczyć, ponieważ o to prosił PO.
phkahler

Złożyłem wszystko w jedną linię, ponieważ odpowiedź agf tak. Byłem zainteresowany tym, czy reduce()jest znacznie szybszy, więc prawie wszystko poza reduce()częścią zrobiłem tak samo, jak agf. Ze względu na czytelność byłoby miło zobaczyć wywołanie funkcji takie jak is_even(n)zamiast wyrażenia n % 2 == 0.
steveha Kwietnia

9

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.


7

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.


2
Nie znajduje wszystkich dzielników, ale tylko czynniki pierwsze, więc nie jest to odpowiedź. Powinieneś pokazać, jak można zbudować wszystkie inne czynniki, a nie tylko powiedzieć, że jest to łatwe! Nawiasem mówiąc, sympy.divisors może lepiej odpowiadać na to pytanie.
Colin Pitrat

Zauważ, że sympy.divisors nie jest dużo szybszy niż przyjęte rozwiązanie.
Colin Pitrat,

@ColinPitrat: Wątpię, czy sympy.divisorsto nie jest dużo szybsze, szczególnie w przypadku liczb z kilkoma dzielnikami. Masz jakieś testy?
Ry-

@Ry Zrobiłem jeden, kiedy napisałem ten komentarz rok temu. Napisanie takiego zajmuje 2 minuty, więc możesz to sprawdzić dwukrotnie.
Colin Pitrat,

3
@ColinPitrat: Sprawdzone. Zgodnie z oczekiwaniami, akceptowana odpowiedź to mniej więcej taka sama prędkość jak sympy.divisorsdla 100 000 i wolniejsza dla czegokolwiek wyższego (kiedy prędkość ma znaczenie). (I oczywiście sympy.divisorsdziała na liczbach takich jak 10000000000000079**2.)
Ry-

7

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

6

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.


Z całą pewnością list.reversejest O (n), a nie O (1), a nie to, że zmienia ogólną złożoność.
agf

Tak to prawda. Popełniłem błąd. Powinien być O (n). (Zaktualizowałem teraz odpowiedź do poprawnej)
Pranjal Mittal

Jest około 2 razy wolniejszy niż rozwiązania @ steveha lub @ agf.
jfs

Możesz uzyskać niewielką (2-3%) poprawę szybkości, powracając l1 + l2.reversed()zamiast odwracać listę w miejscu.
Rakurai

6

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.


Świetne rzeczy! Jeśli umieścisz int (math.sqrt (n)) + 1 poza pętlą for, powinieneś uzyskać z niego nieco większą wydajność, ponieważ nie będziesz musiał ponownie obliczać go po każdej iteracji pętli for
Tristan Forward

3
@TristanForward: Tak nie działają pętle for w Pythonie. xrange(1, int(math.sqrt(n)) + 1)jest oceniany raz.
Ry-

5

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], []))

1
Tak nie jest, jest to niekoniecznie czas kwadratowy. Nie używaj sumani reduce(list.__add__)do spłaszczania listy.
juanpa.arrivillaga

4

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

1
Nie wytwarza wszystkich czynników liczby. Oblicza czynniki pierwsze liczby, np. Dla x=8oczekiwanego[1, 2, 4, 8][2, 2, 2]
:,

11 znajduje się, gdy w kodzie podanym przez @agf znajduje się 9. `i = 9 -> 99% 9 == 0 -> 9 i 99/9 = 11 jest dodawane.
Steinar Lima,

4

Najprostszy sposób na znalezienie czynników liczby:

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

2

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

Stworzyłem projekt na Github: github.com/Pierre-Thibault/Factor .
Pierre Thibault

2

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


1

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.


1

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


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. 

0

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.


Problem z tym rozwiązaniem polega na tym, że sprawdza wiele liczb, które nie mogą być czynnikami - i sprawdza wyższą z każdej pary czynników osobno, gdy już wiesz, że jest to czynnik po znalezieniu mniejszej z pary czynników.
agf

1
@JasonSchorn: Kiedy znajdziesz 2, od razu wiesz, że 10/2 = 5 również jest dzielnikiem, nie ma potrzeby sprawdzania 5 osobno! :)
Moberg

0

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

0

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

Wyniki testu wydajności przy użyciu numpy zamiast pętli for.


1
Jeśli masz zamiar korzystać z biblioteki, równie dobrze możesz wybrać tę właściwą: SymPy, jak widać w odpowiedzi Evgeni Sergeev.
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;
}

Prawie cały algorytm ogranicza zakres do liczby * .5, ale w rzeczywistości ten zakres jest znacznie mniejszy. to faktycznie sqrt liczby. jeśli mamy dolny dzielnik, możemy łatwo uzyskać górny. ponieważ to tylko liczba / dzielnik. dla 16 otrzymuję 4 dla sqrt, a następnie pętlę od 1 do 4. ponieważ 2 jest dzielnikiem dolnej granicy 16, bierzemy 16/2, aby uzyskać 8. jeśli mamy 1, otrzymujemy 16 to (16/1). Wymyśliłem to, ucząc się o rozkładaniu na czynniki pierwsze, więc nie wiem, czy jest opublikowany gdzie indziej, ale działa nawet dla dużych liczb. Mogę zapewnić rozwiązanie w języku Python.
Tangang Atanga

-4

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

Twoja odpowiedź, choć daje właściwy wynik, jest bardzo nieefektywna. Spójrz na zaakceptowaną odpowiedź. Wyjaśnienie, w jaki sposób rozwiązuje problem, zawsze pomaga odpowiedzi być bardziej użyteczną.
Nick,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.