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

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

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

надеюсь, что это помогает. Если у вас есть какие-либо сомнения, не стесняйтесь пинг и я буду рад помочь вам :).

источник: как определить делители числа
радиус круга - и код и изображение

Мне нравится решение Грега, но я хотел бы, чтобы это было больше похоже на 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)

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

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

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

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

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

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)

Не очень быстро, но возвращает делители строка за строкой, как вы хотели, также вы можете сделать список.добавить(n) и перечислить.добавить(номер), если вы действительно хотите