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

Question

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

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

Answer 1

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 избавится от одного из них.

Answer 2

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

Я только что начал решать Project Euler .В некоторых задачах проверка делителей вызывается внутри двух вложенных циклов 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) дополнительные издержки, связанные с этим изменением, могут привести к более длительной работе функции. </p>

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

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

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

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

X = диапазон (1 100 000 1001) (переменный паритет)

Answer 3

Ответ АГФ действительно классный. Я хотел посмотреть, смогу ли я переписать его, чтобы избежать использования 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% быстрее по моим измерениям.

Answer 4

Альтернативный подход к ответу 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

Answer 5

Для 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))

Answer 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 (о) сложность;Намного быстрее использовать list.reverse () в l2, что требует сложности O (n).(Вот как создается python.) После l2.reverse () l2 может быть добавлен к l1, чтобы получить отсортированный список факторов.

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

Answer 7

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

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должно работать так же хорошо.Я не трачу время на проверку дубликатов, потому что дубликаты не могут существовать в наборе независимо.

Answer 8

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

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

Answer 9

Вот альтернатива решению @ 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 без импорта и гораздо более читабельно. Я не проверял производительность этого подхода, но асимптотически он должен быть таким же, и, если производительность является серьезной проблемой, ни одно из решений не является оптимальным.

Answer 10

В 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 - простое , алгоритм принятого ответа никогда не найдет этот фактор.Обратите внимание, что это не просто один за другим;для больших чисел это будет выключено больше.По этой причине лучше избегать чисел с плавающей точкой в ​​алгоритмах такого рода.