Какой наиболее эффективный способ найти все множители числа в Python?
https://stackoverflow.com/questions/6800193
-
22-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Кто-нибудь может объяснить мне эффективный способ нахождения всех множителей числа в 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 избавляется от одного из них.
Другие советы
Решение, представленное @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 = диапазон (1100,1)
Здесь нет существенной разницы, но с большими числами преимущество очевидно:
X = диапазон (1100000,1000) (только нечетные числа)
X = диапазон (2100000 100) (только четные числа)
X = диапазон (1100000 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 скомпилировать его, затем запустил его под командой времени (1) три раза и сохранил лучшее время.
- Уменьшите версию: 11,58 секунды
- Версия иертолс: 11,49 секунды
- Хитрый версия: 11,12 секунды
Обратите внимание, что версия итулс строит кортеж и передает его в Flatten_iter (). Если вместо этого я изменю код для составления списка, он немного замедляется:
- Иереол (список) Версия: 11,62 секунды
Я считаю, что версия функций сложных генераторов является самым быстрым в Python. Но это не очень быстрее, чем версия для уменьшения, примерно на 4% быстрее в зависимости от моих измерений.
Альтернативный подход к ответу АГФ:
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
Я пробовал большинство этих замечательных ответов с 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 должна работать так же хорошо. Я не утруждаюсь тратить время на проверку дубликатов, потому что дубликаты не могут существовать в сборе независимо.
Дальнейшее улучшение решения 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 () L2 может быть добавлен в L1, чтобы получить отсортированный список факторов.
Примечание, L1 содержит я-s, которые увеличиваются. L2 содержит Q.-s, которые уменьшаются. Это причина использования вышеупомянутой идеи.
Вот альтернатива решению @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 без импорта и гораздо более читаемо. Я не проверял производительность этого подхода, но асимптотически он должен быть одинаковым, и если производительность является серьезной проблемой, ни одно решение не является оптимальным.
Для 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))
В SymPy существует отраслевой алгоритм, который называется факторинт:
>>> 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 - простое число, алгоритм принятого ответа никогда не найдет этот фактор.Обратите внимание, что это не просто отдельный случай;для больших чисел он будет отключен еще больше.По этой причине в алгоритмах такого рода лучше избегать чисел с плавающей запятой.
Вот еще один альтернатив без уменьшения, который хорошо работает с большими числами. Оно использует sum Чтобы сгладить список.
def factors(n):
return set(sum([[i, n//i] for i in xrange(1, int(n**0.5)+1) if not n%i], []))
Обязательно возьмите номер больше, чем 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
Вот пример, если вы хотите использовать номер простых числа, чтобы идти намного быстрее. Эти списки легко найти в Интернете. Я добавил комментарии в коде.
# 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).
Ваш максимальный фактор - это не больше, чем ваш номер, так что, скажем
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(x):
return [i for i in range(1,x+1) if x%i==0]
С использованием 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. Он превосходит все другие версии, которые я протестировал, в том числе Dansalmo's, Jason Schorn's, Oxcrock's, Agf's, Steveha's Solutions и Eryksun, хотя Oxrock's, безусловно, самый близкий.
Используйте что -то такое простое, как и следующее понимание списка, отмечая, что нам не нужно тестировать 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
Я был очень удивлен, когда увидел этот вопрос, что никто не использовал 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
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;
}
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.
Я считаю, что это самый простой способ сделать это:
x = 23
i = 1
while i <= x:
if x % i == 0:
print("factor: %s"% i)
i += 1
