Quelle est la meilleure façon d'obtenir tous les diviseurs d'un nombre?

pour développer ce que Shimi a dit, vous ne devriez exécuter votre boucle de 1 à la racine carrée de N. Ensuite, pour trouver la paire, faites n / i , et cela couvrira tout l'espace du problème.

comme nous l'avons également noté, il s'agit d'un problème de NP, ou "difficile". Recherche Exhaustive, la façon dont vous le faites, est à peu près aussi bon qu'il obtient pour des réponses garanties. Ce fait est utilisé par les algorithmes de chiffrement et pour les aider à sécuriser. Si quelqu'un devait résoudre ça problème, la plupart sinon la totalité de notre communication "sécurisée" actuelle serait rendue incertaine.

code 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))

qui devrait sortir une liste comme:

[1, 2, 4, 5, 10, 20, 25, 50, 100]

bien qu'il y ait déjà beaucoup de solutions à cela, je dois vraiment poster ceci:)

celui-ci est:

• lisible
• court
• non incorporé, prêt à copier-coller
• rapide (dans les cas avec beaucoup de facteurs principaux et diviseurs, > 10 fois plus rapide que la solution de Greg)
• python3, python2 et PyPy conforme

Code:

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

je pense que vous pouvez vous arrêter à math.sqrt(n) au lieu de n/2.

je vais vous donner un exemple pour que vous puissiez le comprendre facilement. Maintenant le sqrt(28) est 5.29 donc ceil(5.29) sera 6. Donc si je m'arrête à 6 H, je peux avoir tous les diviseurs. Comment?

voir D'abord le code puis l'image:

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))

maintenant, Voir l'image ci-dessous:

disons que j'ai déjà ajouté 1 à ma liste de diviseurs et je commence par i=2 so

donc à la fin de toutes les itérations comme j'ai ajouté le quotient et le diviseur à ma liste tous les diviseurs de 28 sont peuplés.

Espérons que cette aide. Si vous avez le moindre doute, n'hésitez pas à répondre et je serai heureux de vous aider :).

Source: comment déterminer diviseurs d'un nombre

rayon du cercle - code et image

J'aime bien Greg solution, mais j'aimerais que ce soit plus python. Je pense qu'il serait plus rapide et plus lisible; donc après un moment de codage, je suis sorti avec ça.

Les deux premières fonctions sont nécessaires pour rendre le produit cartésien des listes. Et peut être réutilisé partout où ce problème se pose. Par la route, je devais le programme moi-même, si quelqu'un connaît une solution pour ce problème, n'hésitez pas à me contacter.

" Factorgenerator" maintenant retourne un dictionnaire. Et puis, le dictionnaire est alimentée en "diviseurs", qui l'utilise pour générer premier d'une liste de listes, où chaque liste est la liste des facteurs de la forme p^n avec p premier. Ensuite nous faisons le produit cartésien de ces listes, et nous utilisons finalement la solution de Greg pour générer le diviseur. On les trie et on les renvoie.

je l'ai testé et il semble être un peu plus rapide que la version précédente. Je l'ai testé dans le cadre d'un plus grand programme, donc je ne peux pas vraiment dire comment beaucoup est-il plus rapide.

Pietro Speroni (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. c'est la première fois que je poste à stackoverflow. Je suis impatient pour les commentaires.

adapté de CodeReview , voici une variante qui fonctionne avec 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))

question ancienne, mais voici ma prise:

def divs(n, m):
    if m == 1: return [1]
    if n % m == 0: return [m] + divs(n, m - 1)
    return divs(n, m - 1)

vous pouvez proxy avec:

def divisorGenerator(n):
    for x in reversed(divs(n, n)):
        yield x

NOTE: pour les langues supportées, cela peut être récursif de queue.

Voici une façon intelligente et rapide de le faire pour les nombres jusqu'à et autour de 10* * 16 en Python pur 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))

en supposant que la fonction factors renvoie les facteurs de n (par exemple, factors(60) renvoie la liste [2, 2, 3, 5]), Voici une fonction pour calculer les diviseurs de 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

voici ma solution. Il semble être stupide, mais fonctionne bien...et j'essayais de trouver tous les bons diviseurs donc la boucle a commencé par 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

si vous ne vous souciez que de l'utilisation de listes et que rien d'autre ne vous importe!

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)]

pour moi cela fonctionne très bien et est aussi propre (Python 3)

def divisors(number):
    n = 1
    while(n<number):
        if(number%n==0):
            print(n)
        else:
            pass
        n += 1
    print(number)

pas très rapide mais renvoie les diviseurs ligne par ligne comme vous le vouliez, vous pouvez aussi faire la liste.annexe (n) et liste.si vous avez vraiment envie de