Может кто-нибудь объяснить мне эффективный способ найти все факторы числа в Python (2.7)?
Я могу создать алгоритм для этого, но я думаю, что он плохо закодирован и занимает слишком много времени, чтобы получить результат для большого числа.
Каков наиболее эффективный способ нахождения всех факторов числа в Python?
Ответ 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 я in range(1, int(sqrt(n)) + 1) if n % я == 0 возвращает пару факторов, если остаток при делении n на меньший равен нулю (ему также не нужно проверять более крупный, он просто получает это путем деления n на меньший).
set(...) снаружи избавляет от дубликатов, что происходит только для идеальных квадратов. При n = 4 это вернет 2 раза, поэтому set избавится от одного из них.
Ответ 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) дополнительные служебные данные из этого изменения могут привести к тому, что функция займет больше времени.
Я проверил несколько тестов, чтобы проверить скорость. Ниже приведен код. Чтобы произвести различные графики, я изменил соответственно 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 100 000 1001) (переменная четность)
Ответ 3
Ответ 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 (list): 11.62 секунд
Я считаю, что сложная версия функций генератора является самой быстрой в Python. Но это не намного быстрее, чем сокращенная версия, примерно на 4% быстрее, основываясь на моих измерениях.
Ответ 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
Ответ 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 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 содержит i -s, которые увеличиваются. l2 содержит q -s, которые уменьшаются. Это причина использования вышеупомянутой идеи.
Ответ 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 должно работать так же хорошо. Я не хочу тратить время на проверку дубликатов, потому что дубликаты не могут существовать в наборе независимо.
Ответ 7
Для 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))
Ответ 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], []))
Ответ 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 без импорта и более читаемо. Я не тестировал производительность этого подхода, но асимптотически он должен быть одинаковым, и если производительность является серьезной проблемой, ни одно из решений не является оптимальным.
Ответ 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 - простое число, алгоритм принятого ответа никогда не найдет этот фактор. Обратите внимание, что это не просто один за другим; для больших чисел это будет выключено больше. По этой причине лучше избегать чисел с плавающей точкой в алгоритмах такого рода.
Ответ 11
Обязательно заберите число больше 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
Ответ 12
Вот пример, если вы хотите использовать число простых чисел, чтобы идти намного быстрее. Эти списки легко найти в Интернете. Я добавил комментарии в код.
# 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)]
Ответ 13
потенциально более эффективный алгоритм, чем те, которые представлены здесь уже (особенно, если в 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 (add from __future__ import division).
Ответ 14
ваш максимальный коэффициент не больше вашего номера, так что пусть скажет
def factors(n):
factors = []
for i in range(1, n//2+1):
if n % i == 0:
factors.append (i)
factors.append(n)
return factors
вуаля!
Ответ 15
Самый простой способ найти факторы числа:
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
Ответ 16
Используйте что-то так же просто, как следующее понимание списка, отметив, что нам не нужно проверять 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))). Конечно, это вызывает много ненужных вызовов функций.
Ответ 17
Использование 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, oxrock's, agf, steveha и eryksun, хотя oxrock является самым близким.
Ответ 18
Это мое решение проблемы:
Обратите внимание, что это займет больше времени для больших чисел. Единственная проблема в том, что я знаю только, как программировать в Python 3.x. Я думаю, что единственное, что нужно изменить, - input() в raw_input().
# Sets the number
num = int(input("Enter number to be tested."))
for i in range(1,num): # Tests all numbers from 1 to the num
while (num % i) == 0: ''' If the remainder of the number when it is divided by i is 0'''
print(i) # Prints i
break # Stops it from repeating one number infinitely
else: # After the previous process if done, do this
print("Finished") # Says that the process is finished
input ("Press return/enter to close the program") ''' Closes the program after pressing enter'''
Ответ 19
Я думаю, что для удобства чтения и скорости решение @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
Ответ 20
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)))
if __name__ == "__main__":
n = int(input("enter the number to get factors"))
fact = list(factors(n))
for x in fact:
print(x)
Ответ 21
Я был очень удивлен, когда увидел этот вопрос, что никто не использовал 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
Ответ 22
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;
}
Ответ 23
import math
'''
I applied finding prime factorization to solve this. (Trial Division)
It 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.
Ответ 24
Без использования функции reduce(), которая не является встроенной функцией в Python3:
def factors(n):
res = [f(x) for f in (lambda x: x, lambda x: n // x) for x in range(1, int(n**0.5) + 1) if not n % x]
return set(res) # returns a set to remove the duplicates from res
Ответ 25
Я считаю, что это самый простой способ сделать это:
x = 23
i = 1
while i <= x:
if x % i == 0:
print("factor: %s"% i)
i += 1