Может ли кто-нибудь объяснить мне эффективный способ поиска всех факторов числа в Python (2.7)?
Я могу создать алгоритм для этого, но я думаю, что он плохо закодирован и требует слишком много времени, чтобы получить результат для большого числа.
Может ли кто-нибудь объяснить мне эффективный способ поиска всех факторов числа в Python (2.7)?
Я могу создать алгоритм для этого, но я думаю, что он плохо закодирован и требует слишком много времени, чтобы получить результат для большого числа.
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
избавится от одного из них.
sqrt
- вероятно, это было еще до того, как люди действительно задумались о поддержке Python 3. Я думаю, что сайт, с которого я получил это, попробовал это против __iadd__
, и он был быстрее. Я, кажется, припоминаю кое-что о том, что x**0.5
в какой-то момент был быстрее, чем sqrt(x)
- и так это более надежно.
- person agf; 23.07.2011
factors
функция очень быстрая и удобная, вы ее придумали? Или у вас есть источник этих вкусностей, которым вы можете поделиться? Спасибо.
- person Levon; 10.07.2012
if not n % i
вместо if n % i == 0
- person dansalmo; 08.11.2013
n//i
, но это звучит как хорошая микрооптимизация.
- person agf; 08.11.2013
n//i
. Разве if n % i == 0
не устраняет необходимость в нанесении полов?
- person sthzg; 07.01.2015
/
вернет число с плавающей запятой, даже если оба аргумента являются целыми числами и они точно делятся, то есть 4 / 2 == 2.0
не 2
.
- person agf; 07.01.2015
from functools import reduce
, чтобы это сработало.
- person anonymoose; 02.09.2017
pow()
вместо **
- я считаю, что pow(n,0.5)
- это O (1), тогда как n**0.5
- это O (N). Это может иметь большое значение, посколькуn
становится больше
- person unseen_rider; 08.01.2018
pow(n,0.5)
- это O (1), тогда как n**0.5
- это O (N)»
- person Ry-♦; 17.02.2018
pow()
вызывает или реализует функцию c ++ pow ()
- person unseen_rider; 18.02.2018
**
для возведения в степень значительно медленнее для больших n
.
- person unseen_rider; 18.02.2018
reduce(list.__add__, ...)
- неэффективный способ сгладить список. см. эту суть. Вы могли использовать reduce(list.__iadd__,...,[])
, но это неэлегантно смешивает побочные эффекты с функциональными конструкциями.
- person juanpa.arrivillaga; 23.07.2018
set
для удаления дубликатов?
- person Rakurai; 25.01.2019
if not n%i
- это последовательное ускорение на 20-30% на моем компьютере на n
до 100000 (МБП 2013 г. с i7) с использованием Python 3.6.7. pow**0.5
vs pow(n,0.5)
vs sqrt(n)
, похоже, не имеет никакого значения в моем ограниченном тестировании.
- person Rakurai; 25.01.2019
sqrt
, но это не видно в предоставленном коде. похоже, что правки в блоке кода привели к его смещению.
- person Pod; 28.11.2019
sorted()
, чтобы было чище. Это сложно использовать в математике, если множители волей-неволей.
- person Someone; 14.02.2021
Решение, представленное @agf, великолепно, но можно увеличить время выполнения на ~ 50% для произвольного нечетного числа, проверив четность. Поскольку множители нечетного числа всегда сами нечетны, нет необходимости проверять их при работе с нечетными числами.
Я только что начал решать головоломки Project Euler. В некоторых задачах проверка делителя вызывается внутри двух вложенных for
циклов, поэтому производительность этой функции очень важна.
Объединив этот факт с отличным решением agf, я получил эту функцию:
from functools import reduce
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,100000,1000) (только нечетные числа)
X = диапазон (2,100000,100) (только четные числа)
X = диапазон (1,100000,1001) (переменная четность)
Ответ 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) и сохранил лучшее время.
Обратите внимание, что версия itertools создает кортеж и передает его в flatten_iter (). Если я изменю код для построения списка, он немного замедлится:
Я считаю, что версия сложных функций генератора - самая быстрая из возможных в Python. Но на самом деле это не намного быстрее, чем уменьшенная версия, примерно на 4% быстрее, согласно моим измерениям.
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]}
- person jfs; 02.07.2016
Вот альтернатива решению @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 без импорта и гораздо более читабельно. Я не тестировал производительность этого подхода, но асимптотически он должен быть таким же, и если производительность вызывает серьезную озабоченность, ни одно из решений не является оптимальным.
В 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 является простым, алгоритм принятого ответа никогда не найдет этот коэффициент. Обратите внимание, что это не просто одно за другим; для больших чисел будет больше. По этой причине в алгоритмах такого рода лучше избегать чисел с плавающей запятой.
sympy.divisors
не намного быстрее, особенно для чисел с несколькими делителями. Есть тесты?
- person Ry-♦; 12.08.2018
sympy.divisors
для 100000 и медленнее для всего, что выше (когда скорость действительно имеет значение). (И, конечно же, sympy.divisors
работает с числами вроде 10000000000000079**2
.)
- person Ry-♦; 14.08.2018
Альтернативный подход к ответу 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
reduce()
значительно быстрее, поэтому я почти все, кроме части reduce()
, сделал так же, как и agf. Для удобства чтения было бы неплохо увидеть вызов функции типа is_even(n)
, а не выражение типа n % 2 == 0
.
- person steveha; 09.04.2013
Для 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))
SystemError: deallocated bytearray object has exported buffers
, когда вы помещаете его в файл и запускаете, как обычно, с консоли: py -3 test.py
, когда вы устанавливаете n
на очень большое число, например. n = 326832565659962601981259122112549
. Странная вещь - он работает, когда вы запускаете его прямо из консоли python py -3
, но выдает ошибку при запуске py -3 test.py
- person AlekseyHoffman; 27.11.2020
Самый простой способ найти множители числа:
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
Я попробовал большинство из этих замечательных ответов с 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 также будет работать. Я не беспокоюсь о том, чтобы тратить время на проверку дубликатов, потому что дубликаты не могут существовать в наборе в любом случае.
xrange(1, int(math.sqrt(n)) + 1)
оценивается один раз.
- person Ry-♦; 21.09.2018
xrange
- это Python 2. Он устарел.
- person Someone; 14.02.2021
Дальнейшее улучшение решения афг и эрыксун. Следующий фрагмент кода возвращает отсортированный список всех факторов без изменения асимптотической сложности времени выполнения:
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. l2 содержит убывающие q. Это причина использования вышеупомянутой идеи.
list.reverse
- это O (n), а не O (1), но это не меняет общую сложность.
- person agf; 17.04.2013
l1 + l2.reversed()
вместо того, чтобы переворачивать список на место.
- person Rakurai; 26.01.2019
Вот еще одна альтернатива без сокращения, которая хорошо работает с большими числами. Он использует sum
для выравнивания списка.
def factors(n):
return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
sum
или reduce(list.__add__)
для сглаживания списка.
- person juanpa.arrivillaga; 23.07.2018
Не забудьте взять число больше 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
x=8
expected: [1, 2, 4, 8]
, got: [2, 2, 2]
- person jfs; 28.04.2013
Вот пример, если вы хотите использовать простые числа, чтобы работать намного быстрее. Эти списки легко найти в Интернете. Я добавил в код комментарии.
# 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)]
потенциально более эффективный алгоритм, чем уже представленные здесь (особенно если в 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
).
Использование 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. Он превосходит все другие версии, которые я тестировал, включая растворы дансалмо, Джейсона Шорна, оксрока, агфа, стевехи и эриксуна, хотя оксрок гораздо ближе.
Я был очень удивлен, когда увидел этот вопрос, что никто не использовал 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.
ваш максимальный фактор не больше вашего числа, так что, скажем,
def factors(n):
factors = []
for i in range(1, n//2+1):
if n % i == 0:
factors.append (i)
factors.append(n)
return factors
вуаля!
Если вы не хотите использовать какую-либо библиотеку, я думаю, это самый простой способ сделать
def factors(n):
l=[] #emoty list
# appending the factors in the list
for i in range(1,n+1):
if n%i==0:
l.append(i)
Я программист среднего уровня. Так что в случае, если я ошибаюсь, пожалуйста, поправьте меня
Используйте что-то столь же простое, как следующее понимание списка, отметив, что нам не нужно проверять 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)))
. Конечно, это приводит к множеству ненужных вызовов функций.
Я думаю, что для удобочитаемости и скорости решение @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
цикл до тех пор, пока вы не найдете дубликат в x или v кортежа, где x - знаменатель, а v - результат.
number=30
tuple_list=[]
for i in np.arange(1,number):
if number%i==0:
other=int(number/i)
if any([(x,v) for (x,v) in tuple_list if (i==x) or (i==v)])==True:
break
tuple_list.append((i,other))
flattened = [item for sublist in tuple_list for item in sublist]
print(sorted(flattened))
вывод
[1, 2, 3, 5, 6, 10, 15, 30]
Я нашел простое решение, используя библиотеку cypari в python. Вот ссылка!
import cypari
def get_divisors(n):
divisors = cypari.pari('divisors({})'.format(n))
return divisors
print(get_divisors(24))
вывод
[1, 2, 3, 4, 6, 8, 12, 24]
Я считаю, что это самый простой способ сделать это:
x = 23
i = 1
while i <= x:
if x % i == 0:
print("factor: %s"% i)
i += 1
primefac
? pypi.python.org/pypi/primefac - person Zubo   schedule 02.03.2018primefac
не работает на Python 3. По крайней мере, не на 3.9.4. - person Craig McQueen   schedule 21.04.2021