Каков наилучший способ получить все делители числа?

Question

Вот очень тупой путь:

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: Перестаньте говорить, что это дубликат этой записи. Для вычисления числа делителей заданного числа не нужно вычислять все делители. Это другая проблема, если вы думаете, что это не так, ищите «функцию делителя» в Википедии. Прочтите вопросы и ответ перед публикацией, если вы не понимаете, в чем суть темы, просто не добавляйте бесполезные и уже предоставленные ответы.

Answer 1

Учитывая вашу функцию 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

Общая эффективность этого алгоритма будет полностью зависеть от эффективности фактора генератора.

Answer 2

Чтобы расширить то, что сказал Шими, вы должны выполнять цикл только от 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]

Answer 3

Я думаю, вы можете остановиться на math.sqrt(n) вместо 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 заполняются.

Источник: Как определить делители числа

Answer 4

Хотя уже есть много решений для этого, я действительно должен опубликовать это:)

Это:

• для чтения
• короткий
• автономно, копировать и вставлять готов
• быстро (в случаях с большим количеством простых факторов и делителей,> в 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:
            factors[i] = factors.get(i, 0) + 1
            nn //= i
        i += 1
    if nn > 1:
        factors[nn] = factors.get(nn, 0) + 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

Answer 5

Мне нравится решение Грега, но хотелось бы, чтобы он был больше похож на Python. Я чувствую, что это будет быстрее и более читабельным; так что после некоторого времени кодирования я вышел с этим.

Первые две функции необходимы для создания декартового произведения списков. И может быть повторно использован везде, где возникает эта проблема. Кстати, мне пришлось программировать это самостоятельно, если кто-нибудь знает стандартное решение этой проблемы, пожалуйста, не стесняйтесь связаться со мной.

"Factorgenerator" теперь возвращает словарь. А затем словарь подается в «делители», которые используют его для генерации сначала списка списков, где каждый список представляет собой список факторов вида p ^ n с p prime. Затем мы делаем декартово произведение этих списков и, наконец, используем решение Грега для генерации делителя. Мы сортируем их и возвращаем.

Я проверил это, и оно кажется немного быстрее, чем в предыдущей версии Я проверил это как часть более крупной программы, поэтому я не могу точно сказать, насколько это быстрее.

Пьетро Сперони (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)

P.S. это первый раз, когда я отправляю сообщения в stackoverflow. Я с нетерпением жду каких-либо отзывов.

Answer 6

Адаптировано с 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))

Answer 7

Я просто собираюсь добавить немного пересмотренную версию 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

Answer 8

Вот умный и быстрый способ сделать это для чисел до и около 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))

Answer 9

Старый вопрос, но вот мое мнение:

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

ПРИМЕЧАНИЕ: для языков, которые поддерживают, это может быть хвостовой рекурсией

Answer 10

Если вы заботитесь только об использовании списочных представлений, и для вас больше ничего не важно!

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)