Каков наиболее эффективный способ найти все множители числа в Python?

144

Может ли кто-нибудь объяснить мне эффективный способ найти все факторы числа в Python (2.7)?

Я могу создать алгоритм для этого, но я думаю, что он плохо закодирован и требует слишком много времени, чтобы получить результат для большого числа.

Аднан
источник
3
Я не знаю питона. Но эта страница может быть полезна для вас en.wikipedia.org/wiki/Integer_factorization
Стэн,
3
Как насчет использования primefac? pypi.python.org/pypi/primefac
Zubo 02

Ответы:

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

Это очень быстро вернет все факторы числа n.

Почему квадратный корень является верхним пределом?

sqrt(x) * sqrt(x) = x. Итак, если два фактора совпадают, они оба являются квадратным корнем. Если вы увеличиваете один фактор, вы должны уменьшать другой. Это означает, что один из двух всегда будет меньше или равен sqrt(x), поэтому вам нужно выполнить поиск только до этой точки, чтобы найти один из двух совпадающих факторов. Затем вы можете использовать x / fac1для получения fac2.

Он reduce(list.__add__, ...)берет маленькие списки [fac1, fac2]и объединяет их в один длинный список.

В [i, n/i] for i in range(1, int(sqrt(n)) + 1) if n % i == 0возвращается пара факторов , если остаток при разделении nна меньший равен нулю (это не нужно , чтобы проверить больше один тоже, он просто получает , что при делении nна один меньше.)

set(...)Снаружи избавляются от дубликатов, которая бывает только для идеальных квадратов. Ибо n = 4это вернется 2дважды, поэтому setизбавьтесь от одного из них.

agf
источник
1
Я скопировал это из списка алгоритмов на свой компьютер, все, что я сделал, это инкапсулировал sqrt- вероятно, это было раньше, чем люди действительно думали о поддержке Python 3. Я думаю, что сайт, с которого я получил это, попробовал его, __iadd__и он был быстрее . Кажется, я кое-что припоминаю о том, x**0.5чтобы быть быстрее, чем sqrt(x)в какой-то момент, - и так это более надежно.
agf
9
Кажется, будет работать на 15% быстрее, если я буду использовать if not n % iвместоif n % i == 0
dansalmo
3
@sthzg Мы хотим, чтобы он возвращал целое число, а не число с плавающей запятой, а в Python 3 /будет возвращать число с плавающей запятой, даже если оба аргумента являются целыми числами и они точно делятся, то есть 4 / 2 == 2.0нет 2.
agf 07
7
Я знаю, что это старый вопрос, но в Python 3.x вам нужно добавить, from functools import reduceчтобы это работало.
анонимус 02
5
@unseen_rider: Звучит не так. Можете ли вы предоставить что-нибудь в поддержку этого?
Ry-
57

Решение, представленное @agf, великолепно, но можно добиться ускорения времени выполнения на ~ 50% для произвольного нечетного числа, проверив четность. Поскольку множители нечетного числа всегда сами нечетны, нет необходимости проверять их при работе с нечетными числами.

Я только что начал решать головоломки проекта Эйлер . В некоторых задачах проверка делителя вызывается внутри двух вложенных forциклов, поэтому производительность этой функции очень важна.

Объединив этот факт с отличным решением agf, я получил эту функцию:

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

Однако при небольших числах (~ <100) дополнительные накладные расходы из-за этого изменения могут привести к увеличению времени выполнения функции.

Я провел несколько тестов, чтобы проверить скорость. Ниже приведен используемый код. Чтобы получить разные сюжеты, я соответствующим образом изменил 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 = диапазон (1,100,1) X = диапазон (1,100,1)

Здесь нет существенной разницы, но с большими числами преимущество очевидно:

X = диапазон (1,100000,1000) (только нечетные числа) X = диапазон (1,100000,1000) (только нечетные числа)

X = диапазон (2,100000,100) (только четные числа) X = диапазон (2,100000,100) (только четные числа)

X = диапазон (1,100000,1001) (переменная четность) X = диапазон (1,100000,1001) (переменная четность)

Стейнар Лима
источник
29

Ответ agf действительно классный. Я хотел посмотреть, смогу ли я его переписать, чтобы избежать использования reduce(). Вот что я придумал:

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

Я также пробовал версию, в которой используются хитрые функции генератора:

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)

Я рассчитал это, вычислив:

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

Я запустил его один раз, чтобы Python скомпилировал его, затем трижды запустил с помощью команды time (1) и сохранил лучшее время.

  • уменьшить версию: 11,58 секунды
  • версия itertools: 11,49 секунды
  • хитрая версия: 11,12 секунды

Обратите внимание, что версия itertools создает кортеж и передает его в flatten_iter (). Если я изменю код для построения списка, он немного замедлится:

  • iterools (список) версия: 11.62 секунды

Я считаю, что версия сложных функций генератора является самой быстрой из возможных в Python. Но на самом деле это не намного быстрее, чем уменьшенная версия, примерно на 4% быстрее, согласно моим измерениям.

Стивеха
источник
2
вы можете упростить "хитрую версию" (убрать ненужное 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

Альтернативный подход к ответу 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
Можете ли вы объяснить часть div, mod?
Adnan
3
divmod (x, y) возвращает ((xx% y) / y, x% y), то есть частное и остаток от деления.
c4757p
Это не очень хорошо обрабатывает повторяющиеся факторы - например, попробуйте 81.
phkahler
Ваш ответ более ясен, поэтому я смог его немного разобрать, чтобы понять неправильно. Я думал о разложении на простые множители, когда вы хотели бы назвать несколько троек. Это должно быть нормально, так как это то, о чем просил OP.
phkahler
Я сложил все в одну строку, потому что это сделал ответ agf. Мне было интересно узнать, будет ли reduce()это значительно быстрее, поэтому я почти все, кроме этой reduce()части, делал так же, как и agf. Для удобства чтения было бы неплохо видеть вызов функции как, is_even(n)а не выражение вроде n % 2 == 0.
steveha
10

Вот альтернатива решению @agf, которое реализует тот же алгоритм в более питоническом стиле:

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

Это решение работает как в Python 2, так и в Python 3 без импорта и гораздо более читабельно. Я не тестировал производительность этого подхода, но асимптотически он должен быть таким же, и если производительность вызывает серьезную озабоченность, ни одно из решений не является оптимальным.

Юлиан
источник
10

Для n до 10 ** 16 (может быть, даже немного больше) вот быстрое решение на чистом 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))
Бруно Астролино
источник
9

В SymPy есть надежный в отрасли алгоритм, называемый 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}

Это заняло меньше минуты. Он переключается между коктейлем методов. См. Документацию по ссылке выше.

Учитывая все основные факторы, можно легко построить все остальные факторы.


Обратите внимание, что даже если принятому ответу было разрешено работать достаточно долго (то есть вечность), чтобы разложить указанное выше число, для некоторых больших чисел он не удастся, например, в следующем примере. Это из-за неряшливости int(n**0.5). Например, когда n = 10000000000000079**2у нас есть

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

Поскольку 10000000000000079 - простое число, алгоритм принятого ответа никогда не найдет этот множитель. Обратите внимание, что это не просто одно за другим; для больших чисел будет больше. По этой причине в алгоритмах такого рода лучше избегать чисел с плавающей запятой.

Евгений Сергеев
источник
2
Он не находит все делители, а только простые множители, поэтому на самом деле это не ответ. Вы должны показать, как можно построить все остальные факторы, а не просто сказать, что это просто! Кстати, sympy.divisors может лучше ответить на этот вопрос.
Колин Питрат 09
И обратите внимание, что sympy.divisors ненамного быстрее принятого решения.
Colin Pitrat 09
@ColinPitrat: Я как бы сомневаюсь, что sympy.divisorsэто не намного быстрее, особенно для чисел с несколькими делителями. Есть тесты?
Ry-
@Ry Я сделал это, когда писал этот комментарий год назад. Написание одного занимает 2 минуты, так что не стесняйтесь перепроверить.
Колин Питрат
4
@ColinPitrat: Проверено. Как и ожидалось, принятый ответ примерно такой же, как sympy.divisorsдля 100000, и медленнее для всего, что выше (когда скорость действительно имеет значение). (И, конечно, sympy.divisorsработает с числами вроде 10000000000000079**2.)
Ry-
6

Дальнейшее улучшение решения afg & eryksun. Следующий фрагмент кода возвращает отсортированный список всех факторов без изменения асимптотической сложности времени выполнения:

    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

Идея: вместо использования функции list.sort () для получения отсортированного списка, который дает сложность nlog (n); Намного быстрее использовать list.reverse () на l2, который занимает O (n) сложность. (Так создается python.) После l2.reverse () к l1 можно добавить l2, чтобы получить отсортированный список факторов.

Обратите внимание, что l1 содержит i- s, которые увеличиваются. l2 содержит q -s, которые убывают. Это причина использования вышеупомянутой идеи.

Пранджал Миттал
источник
Совершенно уверен, что list.reverseO (n), а не O (1), не то, что это меняет общую сложность.
agf
Да все верно. Я допустил ошибку. Должно быть O (n). (Я обновил ответ на правильный)
Пранджал Миттал
Это примерно в 2 раза медленнее, чем решения @ steveha или @ agf.
jfs
Вы можете получить небольшое (2-3%) улучшение скорости, вернув l1 + l2.reversed()список вместо того, чтобы перевернуть его.
Rakurai
6

Я попробовал большинство из этих замечательных ответов с timeit, чтобы сравнить их эффективность с моей простой функцией, и все же я постоянно вижу, что мои результаты превосходят перечисленные здесь. Я подумал, что поделюсь этим и посмотрю, что вы все думаете.

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

Как написано, вам придется импортировать математику для проверки, но замена math.sqrt (n) на n **. 5 также будет работать. Я не трачу время на проверку дубликатов, потому что в любом случае дубликаты не могут существовать в наборе.

Oxrock
источник
Отличный материал! Если вы поместите int (math.sqrt (n)) + 1 вне цикла for, вы должны получить от него немного больше производительности, поскольку вам не придется повторно вычислять его на каждой итерации цикла for
Тристан Форвард,
3
@TristanForward: Циклы for в Python работают не так. xrange(1, int(math.sqrt(n)) + 1)оценивается один раз.
Ry-
5

Вот еще один вариант без сокращения, который хорошо работает с большими числами. Используется sumдля сглаживания списка.

def factors(n):
    return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
Дансалмо
источник
1
Это не так, это чрезмерно квадратичное время. Не используйте sumили reduce(list.__add__)для сглаживания списка.
juanpa.arrivillaga
5

Самый простой способ найти множители числа:

def factors(x):
    return [i for i in range(1,x+1) if x%i==0]
GooDeeJaY
источник
4

Обязательно возьмите число больше, чем sqrt(number_to_factor)для необычных чисел, таких как 99, в котором есть 3 * 3 * 11 и 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
источник
1
Он не производит всех множителей числа. Он вычисляет простые множители числа, например, для x=8ожидаемого:, [1, 2, 4, 8]получил:[2, 2, 2]
jfs
11 обнаруживается, когда 9 входит в код, заданный @agf. ʻI = 9 -> 99% 9 == 0 -> 9 и 99/9 = 11 добавлено.
Steinar Lima
2

Вот пример, если вы хотите использовать число простых чисел, чтобы работать намного быстрее. Эти списки легко найти в Интернете. Я добавил комментарии в код.

# 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)]
Пьер Тибо
источник
Я создал проект на Github: github.com/Pierre-Thibault/Factor .
Пьер Тибо
2

потенциально более эффективный алгоритм, чем уже представленные здесь (особенно, если есть небольшие простые фактоны n). Хитрость здесь в том, чтобы регулировать предел, до которого требуется пробное деление каждый раз, когда обнаруживаются простые множители:

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

это, конечно, все еще пробное деление и ничего лишнего. и поэтому по-прежнему очень ограничен в своей эффективности (особенно для больших чисел без малых делителей).

это python3; разделение //должно быть единственным, что вам нужно адаптировать для Python 2 (добавить from __future__ import division).

Хиро главный герой
источник
1

Использование set(...)делает код немного медленнее и действительно необходимо только тогда, когда вы проверяете квадратный корень. Вот моя версия:

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:Условие необходимо для чисел , как 12, где квадратный корень не является целым числом, но пол квадратного корня является фактором.

Обратите внимание, что эта версия не возвращает сам номер, но это легко исправить, если вы этого хотите. Вывод также не сортируется.

Я рассчитал его запуск 10000 раз для всех номеров 1-200 и 100 раз для всех номеров 1-5000. Он превосходит все другие версии, которые я тестировал, включая растворы дансалмо, Джейсона Шорна, оксрока, агфа, стевехи и эриксуна, хотя оксрок гораздо ближе.

HamsterBoo
источник
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

Используйте что-то столь же простое, как следующее понимание списка, отметив, что нам не нужно проверять 1 и число, которое мы пытаемся найти:

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

Что касается использования квадратного корня, скажем, мы хотим найти множители 10. Целая часть sqrt(10) = 4следовательно range(1, int(sqrt(10))) = [1, 2, 3, 4]и проверка до 4 явно пропускают 5.

Если я не упускаю что-то, я бы предложил, если вы должны сделать это таким образом, используя int(ceil(sqrt(x))). Конечно, это приводит к множеству ненужных вызовов функций.

Джейсон Шорн
источник
Проблема с этим решением заключается в том, что оно проверяет множество чисел, которые, возможно, не могут быть факторами, и проверяет большее значение каждой пары факторов отдельно, когда вы уже знаете, что это фактор, после нахождения меньшего из пары факторов.
agf
1
@JasonSchorn: Когда вы найдете 2, вы сразу поймете, что 10/2 = 5 также является делителем, не нужно проверять 5 отдельно! :)
Moberg
0

Я думаю, что для удобочитаемости и скорости решение @oxrock является лучшим, поэтому вот код, переписанный для 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
Ник Скоццаро
источник
0

Я был очень удивлен, когда увидел этот вопрос, что никто не использовал numpy, даже если numpy намного быстрее, чем циклы python. Реализовав решение @agf с numpy, оно оказалось в среднем в 8 раз быстрее . Я верю, что если вы реализовали некоторые другие решения в numpy, у вас были бы потрясающие времена.

Вот моя функция:

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

Обратите внимание, что числа на оси x не являются входными данными для функций. Входными данными для функций является 2 к числу на оси x минус 1. Таким образом, если десять - это вход, будет 2 ** 10-1 = 1023.

Результаты теста производительности использования numpy вместо циклов for.

Бенедикт Вильджи Магнуссон
источник
1
Если вы собираетесь использовать библиотеку, можете сделать ее правильной: SymPy, как видно из ответа Евгения Сергеева.
Ry-
0

ваш максимальный фактор не больше вашего числа, так что, скажем,

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

    return factors

вуаля!

Полина Новикова
источник
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;
}
Танганг Атанга
источник
Почти весь алгоритм здесь ограничивает диапазон числом * .5, но на самом деле этот диапазон намного меньше. это на самом деле sqrt числа. если у нас есть нижний делитель, мы можем легко получить верхний. так как это просто число / делитель. для 16 я получаю 4 для sqrt, затем перебираю от 1 до 4. Поскольку 2 является нижним делителем 16, мы берем 16/2, чтобы получить 8. если у нас есть 1, то для получения 16 будет (16/1). Я придумал это, когда узнал о простой факторизации, поэтому я не знаю, опубликован ли он где-то еще, но он работает даже для больших чисел. Я могу предоставить решение на Python.
Tangang Atanga
-4

Я считаю, что это самый простой способ сделать это:

    x = 23

    i = 1
    while i <= x:
      if x % i == 0:
        print("factor: %s"% i)
      i += 1
DeDude
источник
Ваш ответ, хотя и дает правильный результат, очень неэффективен. Взгляните на принятый ответ. Объяснение того, как он решает проблему, всегда помогает сделать ответ более полезным.
Ник