Какой самый эффективный способ найти все факторы числа в Python?
Может кто-нибудь объяснить мне эффективный способ найти все факторы числа в Python (2.7)?
Я могу создать алгоритмы для этой работы, но я думаю, что она плохо закодирована и занимает слишком много времени, чтобы выполнить результат для большого числа.
31 ответ
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 = диапазон (1 100,1)
Здесь нет существенной разницы, но с большими числами преимущество очевидно:
X = диапазон (1 100 000 1000) (только нечетные числа)
X = диапазон (2 100 000 100) (только четные числа)
X = диапазон (1 100 000 1001) (переменный паритет)
В 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 - простое число, алгоритм принятого ответа никогда не найдет этот фактор. Обратите внимание, что это не просто один за другим; для больших чисел это будет выключено больше. По этой причине лучше избегать чисел с плавающей точкой в алгоритмах такого рода.
Ответ АГФ действительно очень крутой. Я хотел посмотреть, смогу ли я переписать его, чтобы избежать использования 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% быстрее, по моим измерениям.
Вот альтернатива решению @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))
Альтернативный подход к ответу 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
Самый простой способ найти множители числа:
def factors(x):
return [i for i in range(1,x+1) if x%i==0]
Я попробовал большинство из этих замечательных ответов со временем, чтобы сравнить их эффективность с моей простой функцией, и все же я постоянно вижу, что мои результаты превосходят перечисленные здесь. Я решил поделиться этим и посмотреть, что вы все думаете.
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 для тестирования, но замена 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 содержит i- s, которые увеличиваются. l2 содержит q-s, которые убывают. Вот причина использования вышеупомянутой идеи.
Недавно я разработал новый подход к факторизации целых чисел, который называется Smooth Subsum Search (SSS). Вот моя реализация на Python: https://github.com/sbaresearch/smoothsubsumsearch
Он может факторизовать 30-значные числа примерно за 0,2 секунды, 40-значные числа примерно за 2 секунды, 50-значные числа примерно за 30 секунд, 60-значные числа примерно за 200 секунд и 70-значные числа примерно за 3000 секунд. По сравнению с реализацией самоинициализирующегося квадратичного сита в Sympy, которая является наиболее эффективной реализацией квадратичного сита в Python, которую я смог найти, она работает примерно в 5–7 раз быстрее. SSS очень подробно описан в: https://arxiv.org/abs/2301.10529 .
Вот еще одна альтернатива без сокращения, которая хорошо работает с большими числами. Оно использует 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)]
Хотя в вопросе говорится о Python (2.7), людей может заинтересовать это простое решение с использованием Numpy.
import numpy as np
t=np.arange(2,n,1)
t[n%t==0]
Это не вернется
1ни сам номер. Таким образом, он вернет пустой массив, если
nявляется простым.
Я немного удивлен, что не смог найти простой реализации целочисленной простой факторизации в виде
from collections import defaultdict
from itertools import count
def factorize(n):
factors = defaultdict(int)
for i in count(2):
while n % i == 0:
factors[i] += 1
n /= i
if n == 1:
return factors
Эта функция возвращает словарь, в котором ключи являются простыми множителями, а значения — показателями степени. Так, например:
>>> factorize(608)
defaultdict(<class 'int'>, {2: 5, 19: 1})
>>> factorize(1152)
defaultdict(<class 'int'>, {2: 7, 3: 2})
>>> factorize(1088)
defaultdict(<class 'int'>, {2: 6, 17: 1})
Очевидно, что это не самая эффективная реализация — во-первых, она выполняет итерацию по всему набору натуральных чисел, а не сразу к простым, — но она достаточно хороша для относительно небольших значений и достаточно проста, чтобы ее можно было легко понять.
Потенциально более эффективный алгоритм, чем те, что представлены здесь (особенно, если в 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).
Я нашел простое решение, используя библиотеку 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]
Если вы не хотите использовать какую-либо библиотеку, я думаю, это самый простой способ сделать
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)
Я программист среднего уровня. Так что в случае, если я ошибаюсь, пожалуйста, поправьте меня
Ваш максимальный фактор не больше вашего числа, так что, скажем,
def factors(n):
factors = []
for i in range(1, n//2+1):
if n % i == 0:
factors.append (i)
factors.append(n)
return factors
вуаля!
Мы можем использовать следующую лямбда-функцию,
factor = lambda x:[(ele,x/ele) for ele in range(1,x//2+1) if x%ele==0 ]
фактор(10)
вывод: [(1, 10.0), (2, 5.0), (5, 2.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. Он превосходит все остальные версии, которые я тестировал, включая решения Дансалмо, Джейсона Шорна, Oxrock, Agf, Steveha и Eryksun, хотя Oxrock на сегодняшний день наиболее близок.
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.
Я был очень удивлен, когда увидел этот вопрос, что никто не использовал 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 от числа на оси х минус 1. Так что, где десять - это входное значение будет 2**10-1 = 1023
Используйте что-то простое, например, следующее понимание списка, отметив, что нам не нужно проверять 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))), Конечно, это приводит к множеству ненужных вызовов функций.
цикл до тех пор, пока вы не найдете дубликат в 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]
Учитывая, что число положительное целое, вы можете использовать этот подход:
number = int(input("Enter a positive number to find factors: "))
factor = [num for num in range(1,number+1) if number % num == 0]
for fac in factor: print(f"{fac} is a factor of {number}")
Я думаю, что для удобочитаемости и скорости решение @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
Без использования 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
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;
}