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

Question

Voici la méthode la plus stupide :

def divisorGenerator(n):
    for i in xrange(1,n/2+1):
        if n%i == 0: yield i
    yield n

Le résultat que j'aimerais obtenir est similaire à celui-ci, mais j'aimerais un algorithme plus intelligent (celui-ci est trop lent et stupide :-)

Je peux trouver les facteurs premiers et leur multiplicité assez rapidement. J'ai un générateur qui génère des facteurs de cette façon :

(facteur1, multiplicité1)
(facteur2, multiplicité2)
(facteur3, multiplicité3)
et ainsi de suite...

c'est-à-dire la sortie de

for i in factorGenerator(100):
    print i

est :

(2, 2)
(5, 2)

Je ne sais pas dans quelle mesure c'est utile pour ce que je veux faire (je l'ai codé pour d'autres problèmes), de toute façon j'aimerais une façon plus intelligente de faire de la

for i in divisorGen(100):
    print i

sortir ça :

1
2
4
5
10
20
25
50
100

---

UPDATE : Un grand merci à Greg Hewgill et à sa "méthode intelligente" :) Calculer tous les diviseurs de 100000000 a pris 0.01s avec sa méthode contre les 39s que la méthode idiote a pris sur ma machine, très cool :D

UPDATE 2 : Arrêtez de dire que c'est une copie de este post. Calculer le nombre de diviseurs d'un nombre donné ne nécessite pas de calculer tous les diviseurs. C'est un problème différent, si vous pensez que ce n'est pas le cas, cherchez "Fonction diviseur" sur wikipedia. Lisez les questions et les réponses avant de poster, si vous ne comprenez pas le sujet, n'ajoutez pas de réponses inutiles et déjà données.

Answer 1

Compte tenu de votre factorGenerator voici une fonction divisorGen qui devrait fonctionner :

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

L'efficacité globale de cet algorithme dépendra entièrement de l'efficacité de l'algorithme de la factorGenerator .

Answer 2

Pour développer ce que Shimi a dit, vous ne devriez exécuter votre boucle que 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 on l'a également noté, il s'agit d'un problème NP, ou "difficile". La recherche exhaustive, telle que vous la pratiquez, est à peu près la meilleure façon d'obtenir des réponses garanties. Ce fait est utilisé par les algorithmes de cryptage et autres pour aider à les sécuriser. Si quelqu'un parvenait à résoudre ce problème, la plupart, sinon la totalité, de nos communications "sécurisées" actuelles ne seraient plus sûres.

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

Ce qui devrait produire une liste comme :

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

Answer 3

J'aime la solution Greg, mais j'aimerais qu'elle soit plus proche de Python. Je pense que ce serait plus rapide et plus lisible ; donc après un certain temps de codage, j'ai abouti à ceci.

Les deux premières fonctions sont nécessaires pour faire le produit cartésien de listes. Et peuvent être réutilisées à chaque fois que ce problème se présente. A propos, j'ai dû programmer cela moi-même, si quelqu'un connaît une solution standard pour ce problème, n'hésitez pas à me contacter.

"Factorgenerator" retourne maintenant un dictionnaire. Ensuite, le dictionnaire est introduit dans "divisors", qui l'utilise pour générer d'abord 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 enfin la solution de Greg pour générer le diviseur. Nous les trions, et les retournons.

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 programme plus important, je ne peux donc pas vraiment dire dans quelle mesure il est 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 sur stackoverflow. Je suis impatient de recevoir des commentaires.

Answer 4

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

Answer 5

En supposant que le factors renvoie les facteurs de n (par exemple, factors(60) renvoie la liste [2, 2, 3, 5]), voici une fonction permettant de 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