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

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

Вот мое решение. Кажется, это глупо, но работает хорошо ... и я пытался найти все правильные делители, поэтому цикл начался с 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

Answer 2

Для меня это прекрасно работает и тоже чисто (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 (число), если вы действительно хотите

Answer 3

return [x for x in range(n+1) if n/x==int(n/x)]

Answer 4

Предполагая, что функция 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