Каков наилучший способ получить все делители числа?
Вот очень тупой способ:
def divisorGenerator(n):
for i in xrange(1,n/2+1):
if n%i == 0: yield i
yield n
Результат, который я хотел бы получить, похож на этот, но я бы хотел более умный алгоритм (этот слишком медленный и тупой:-)
Я могу найти основные факторы и их кратность достаточно быстро. У меня есть генератор, который генерирует фактор таким образом:
(фактор1, кратность1)
(фактор2, кратность2)
(фактор3, кратность3)
и так далее...
то есть выход
for i in factorGenerator(100):
print i
является:
(2, 2)
(5, 2)
Я не знаю, насколько это полезно для того, что я хочу сделать (я кодировал для других проблем), в любом случае, я хотел бы сделать более умный способ
for i in divisorGen(100):
print i
выведите это:
1
2
4
5
10
20
25
50
100
ОБНОВЛЕНИЕ: Большое спасибо Грегу Хьюгиллу и его "умному способу":) Расчет всех делителей 100000000 занял 0,01 с его счетом против 39 с, которые тупой путь взял на моей машине, очень круто:D
ОБНОВЛЕНИЕ 2: Перестаньте говорить, что это дубликат этого поста. Для вычисления числа делителей заданного числа не нужно вычислять все делители. Это другая проблема, если вы думаете, что это не так, поищите "функцию делителя" в Википедии. Прочтите вопросы и ответ перед публикацией, если вы не понимаете, в чем заключается тема, просто не добавляйте не полезные и уже предоставленные ответы.
19 ответов
Учитывая вашу функцию factorGenerator, вот divisorGen, который должен работать:
def divisorGen(n):
factors = list(factorGenerator(n))
nfactors = len(factors)
f = [0] * nfactors
while True:
yield reduce(lambda x, y: x*y, [factors[x][0]**f[x] for x in range(nfactors)], 1)
i = 0
while True:
f[i] += 1
if f[i] <= factors[i][1]:
break
f[i] = 0
i += 1
if i >= nfactors:
return
Общая эффективность этого алгоритма будет полностью зависеть от эффективности фактора генератора.
Чтобы расширить то, что сказал Шими, вы должны запустить цикл только от 1 до квадратного корня из n. Затем, чтобы найти пару, сделайте n / i, и это покроет все проблемное пространство.
Как также было отмечено, это NP или "трудная" проблема. Исчерпывающий поиск, то, как вы это делаете, примерно так же хорош, как и для гарантированных ответов. Этот факт используется алгоритмами шифрования и т.п. для их защиты. Если бы кто-то решил эту проблему, большинство, если не все наши нынешние "безопасные" коммуникации были бы небезопасными.
Код Python:
import math
def divisorGenerator(n):
large_divisors = []
for i in xrange(1, int(math.sqrt(n) + 1)):
if n % i == 0:
yield i
if i*i != n:
large_divisors.append(n / i)
for divisor in reversed(large_divisors):
yield divisor
print list(divisorGenerator(100))
Который должен вывести список вроде:
[1, 2, 4, 5, 10, 20, 25, 50, 100]
Я думаю, что вы можете остановиться на math.sqrt(n) вместо н /2.
Я приведу вам пример, чтобы вы могли его легко понять. Теперь sqrt(28) является 5.29 так ceil(5.29) будет 6. Так что я, если я остановлюсь на 6, то я смогу получить все делители. Как?
Сначала посмотрите код, а затем увидите изображение:
import math
def divisors(n):
divs = [1]
for i in xrange(2,int(math.sqrt(n))+1):
if n%i == 0:
divs.extend([i,n/i])
divs.extend([n])
return list(set(divs))
Теперь посмотрите на изображение ниже:
Допустим, я уже добавил 1 в мой список делителей, и я начинаю с i=2 так
Таким образом, в конце всех итераций, поскольку я добавил частное и делитель в мой список, все делители 28 заполняются.
Надеюсь это поможет. Если у вас есть какие-либо сомнения, не стесняйтесь отзвонить, и я буду рад помочь вам:).
Источник: Как определить делители числа
Радиус круга - и код и изображение
Хотя уже есть много решений для этого, я действительно должен опубликовать это:)
Этот:
- удобочитаемый
- короткая
- автономный, копировать и вставлять готов
- быстро (в случаях с большим количеством простых факторов и делителей> в 10 раз быстрее, чем решение Грега)
- совместимый с python3, python2 и pypy
Код:
def divisors(n):
# get factors and their counts
factors = {}
nn = n
i = 2
while i*i <= nn:
while nn % i == 0:
if not i in factors:
factors[i] = 0
factors[i] += 1
nn //= i
i += 1
if nn > 1:
factors[nn] = 1
primes = list(factors.keys())
# generates factors from primes[k:] subset
def generate(k):
if k == len(primes):
yield 1
else:
rest = generate(k+1)
prime = primes[k]
for factor in rest:
prime_to_i = 1
# prime_to_i iterates prime**i values, i being all possible exponents
for _ in range(factors[prime] + 1):
yield factor * prime_to_i
prime_to_i *= prime
# in python3, `yield from generate(0)` would also work
for factor in generate(0):
yield factor
Я просто собираюсь добавить немного пересмотренную версию Anivarth's (поскольку я считаю, что она наиболее питонна) для дальнейшего использования.
from math import sqrt
def divisors(n):
divs = {1,n}
for i in range(2,int(sqrt(n))+1):
if n%i == 0:
divs.update((i,n//i))
return divs
Мне нравится решение Грега, но хотелось бы, чтобы он был больше похож на Python. Я чувствую, что это будет быстрее и более читабельным; так что после некоторого времени кодирования я вышел с этим.
Первые две функции необходимы, чтобы сделать декартово произведение списков. И может быть использован повторно везде, где возникает эта проблема. Кстати, мне пришлось программировать это сам, если кто-нибудь знает стандартное решение этой проблемы, пожалуйста, не стесняйтесь связаться со мной.
"Factorgenerator" теперь возвращает словарь. А затем словарь подается в "делители", которые используют его для генерации сначала списка списков, где каждый список представляет собой список факторов вида p^n с p простым числом. Затем мы делаем декартово произведение этих списков и, наконец, используем решение Грега для генерации делителя. Мы сортируем их и возвращаем.
Я проверил это, и это кажется немного быстрее, чем в предыдущей версии. Я проверил это как часть более крупной программы, поэтому не могу сказать, насколько это быстрее.
Пьетро Сперони (Pietrosperoni dot it)
from math import sqrt
##############################################################
### cartesian product of lists ##################################
##############################################################
def appendEs2Sequences(sequences,es):
result=[]
if not sequences:
for e in es:
result.append([e])
else:
for e in es:
result+=[seq+[e] for seq in sequences]
return result
def cartesianproduct(lists):
"""
given a list of lists,
returns all the possible combinations taking one element from each list
The list does not have to be of equal length
"""
return reduce(appendEs2Sequences,lists,[])
##############################################################
### prime factors of a natural ##################################
##############################################################
def primefactors(n):
'''lists prime factors, from greatest to smallest'''
i = 2
while i<=sqrt(n):
if n%i==0:
l = primefactors(n/i)
l.append(i)
return l
i+=1
return [n] # n is prime
##############################################################
### factorization of a natural ##################################
##############################################################
def factorGenerator(n):
p = primefactors(n)
factors={}
for p1 in p:
try:
factors[p1]+=1
except KeyError:
factors[p1]=1
return factors
def divisors(n):
factors = factorGenerator(n)
divisors=[]
listexponents=[map(lambda x:k**x,range(0,factors[k]+1)) for k in factors.keys()]
listfactors=cartesianproduct(listexponents)
for f in listfactors:
divisors.append(reduce(lambda x, y: x*y, f, 1))
divisors.sort()
return divisors
print divisors(60668796879)
PS Это первый раз, когда я отправляю сообщения в stackru. Я с нетерпением жду каких-либо отзывов.
Вот умный и быстрый способ сделать это для чисел до и около 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))
Если на вашем компьютере много памяти, простая простая строка может быть достаточно быстрой с помощью numpy:
N = 10000000; tst = np.arange(1, N); tst[np.mod(N, tst) == 0]
Out:
array([ 1, 2, 4, 5, 8, 10, 16,
20, 25, 32, 40, 50, 64, 80,
100, 125, 128, 160, 200, 250, 320,
400, 500, 625, 640, 800, 1000, 1250,
1600, 2000, 2500, 3125, 3200, 4000, 5000,
6250, 8000, 10000, 12500, 15625, 16000, 20000,
25000, 31250, 40000, 50000, 62500, 78125, 80000,
100000, 125000, 156250, 200000, 250000, 312500, 400000,
500000, 625000, 1000000, 1250000, 2000000, 2500000, 5000000])
На моем медленном ПК занимает менее 1 секунды.
Старый вопрос, но вот мое взятие:
def divs(n, m):
if m == 1: return [1]
if n % m == 0: return [m] + divs(n, m - 1)
return divs(n, m - 1)
Вы можете прокси с:
def divisorGenerator(n):
for x in reversed(divs(n, n)):
yield x
ПРИМЕЧАНИЕ: для языков, которые поддерживают, это может быть хвостовой рекурсивностью.
Адаптировано из CodeReview, вот вариант, который работает с num=1!
from itertools import product
import operator
def prod(ls):
return reduce(operator.mul, ls, 1)
def powered(factors, powers):
return prod(f**p for (f,p) in zip(factors, powers))
def divisors(num) :
pf = dict(prime_factors(num))
primes = pf.keys()
#For each prime, possible exponents
exponents = [range(i+1) for i in pf.values()]
return (powered(primes,es) for es in product(*exponents))
def divisorGen(n): v = n last = [] for i in range(1, v+1) : if n % i == 0 : last.append(i)
Предполагая, что factors функция возвращает множители n (например, factors(60) возвращает список [2, 2, 3, 5]), здесь есть функция для вычисления делителей n:
function divisors(n)
divs := [1]
for fact in factors(n)
temp := []
for div in divs
if fact * div not in divs
append fact * div to temp
divs := divs + temp
return divs
Вот мое решение. Это кажется глупым, но работает хорошо... и я пытался найти все правильные делители, поэтому цикл начался с i = 2.
import math as m
def findfac(n):
faclist = [1]
for i in range(2, int(m.sqrt(n) + 2)):
if n%i == 0:
if i not in faclist:
faclist.append(i)
if n/i not in faclist:
faclist.append(n/i)
return facts
Если вы заботитесь только об использовании списочных представлений, и ничто другое не имеет для вас значения!
from itertools import combinations
from functools import reduce
def get_devisors(n):
f = [f for f,e in list(factorGenerator(n)) for i in range(e)]
fc = [x for l in range(len(f)+1) for x in combinations(f, l)]
devisors = [1 if c==() else reduce((lambda x, y: x * y), c) for c in set(fc)]
return sorted(devisors)
Попробуйте вычислить квадратный корень из заданного числа, а затем зациклить диапазон (1, квадратный_корень +1).
number = int(input("Enter a Number: "))
square_root = round(number ** (1.0 / 2))
print(square_root)
divisor_list = []
for i in range(1,square_root+1):
if number % i == 0: # Check if mod return 0 if yes then append i and number/i in the list
divisor_list.append(i)
divisor_list.append(int(number/i))
print(divisor_list)
Я не понимаю, почему существует так много сложных решений этой проблемы.
Вот мой взгляд на это:
def divisors(n):
lis =[1]
s = math.ceil(math.sqrt(n))
for g in range(s,1, -1):
if n % g == 0:
lis.append(g)
lis.append(int(n / g))
return (set(lis))
Для меня это работает нормально, а также чисто (Python 3)
def divisors(number):
n = 1
while(n<number):
if(number%n==0):
print(n)
else:
pass
n += 1
print(number)
Не очень быстро, но возвращает делители построчно, как вы хотели, также вы можете сделать list.append(n) и list.append (число), если вы действительно хотите
Мое решение с помощью функции генератора:
def divisor(num):
for x in range(1, num + 1):
if num % x == 0:
yield x
while True:
yield None