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

Вот самый тупой способ:

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

Учитывая вашу 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

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

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

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

Этот:

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

Думаю, можно остановиться на 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 заполнены.

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

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

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

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

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

Пьетро Сперони (расставил все точки над пиетросперони)

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 это первый раз, когда я публикую в stackoverflow. Жду любых отзывов.

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

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

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

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

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

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

Предполагая, что 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)

Если на вашем компьютере много памяти, простой простой строки может быть достаточно с 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 divisor(num):
    for x in range(1, num + 1):
        if num % x == 0:
            yield x
    while True:
        yield None

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

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