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

Voici la manière très 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 assez rapidement les facteurs premiers et leur multiplicité. J'ai un générateur qui génère un facteur de cette manière:

(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 à quel point cela 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

for i in divisorGen(100):
    print i

sortie ceci:

1
2
4
5
10
20
25
50
100

MISE À JOUR: Un grand merci à Greg Hewgill et sa "manière intelligente" :) Le calcul de tous les diviseurs de 100000000 a pris 0,01s avec son chemin contre les 39 que la manière stupide a pris sur ma machine, très cool: D

MISE À JOUR 2: Arrêtez de dire que c'est un double de ce message. Le calcul du nombre de diviseurs d'un nombre donné n'a pas besoin 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 la réponse avant de poster, si vous ne comprenez pas quel est le sujet, n'ajoutez simplement pas les réponses inutiles et déjà données.

Compte tenu de votre factorGeneratorfonction, voici un divisorGenqui 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é du factorGenerator.

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, comme vous le faites, est à peu près aussi bonne que possible pour obtenir des réponses garanties. Ce fait est utilisé par les algorithmes de cryptage et autres pour aider à les sécuriser. Si quelqu'un résolvait ce problème, la plupart sinon la totalité de nos communications «sécurisées» actuelles seraient rendues non sécurisées.

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 afficher une liste comme:

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

Bien qu'il existe déjà de nombreuses solutions à cela, je dois vraiment poster ceci :)

Celui-ci est:

• lisible
• court
• autonome, prêt pour le copier-coller
• rapide (dans les cas avec beaucoup de facteurs premiers et de diviseurs,> 10 fois plus rapide que la solution acceptée)
• Compatible python3, python2 et pypy

Code:

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

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

Je vais vous donner un exemple pour que vous puissiez le comprendre facilement. Maintenant , le sqrt(28)est 5.29donc ceil(5.29)sera 6. Je si je vais arrêter à 6 alors je peux obtenir tous les diviseurs. Comment?

Voir d'abord le code, puis voir 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, voyez l'image ci-dessous:

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

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 remplis.

Source: Comment déterminer les diviseurs d'un nombre

J'aime la solution de Greg, mais j'aurais aimé qu'elle ressemble plus à Python. Je pense que ce serait plus rapide et plus lisible; donc après un certain temps de codage, je suis sorti avec ceci.

Les deux premières fonctions sont nécessaires pour faire le produit cartésien de listes. Et peut être réutilisé dès que ce problème survient. Au fait, j'ai dû le programmer moi-même, si quelqu'un connaît une solution standard pour ce problème, n'hésitez pas à me contacter.

"Factorgenerator" renvoie maintenant un dictionnaire. Et puis le dictionnaire est introduit dans des "diviseurs", qui l'utilisent 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 finalement 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 vaste, donc je ne peux pas vraiment dire à quel point c'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)

PS, c'est la première fois que je poste sur stackoverflow. J'attends vos commentaires avec impatience.

Voici un moyen intelligent et rapide de le faire pour les nombres jusqu'à et autour de 10 ** 16 en pur 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))

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

Je vais juste ajouter une version légèrement révisée d'Anivarth (car je crois que c'est la plus pythonique) pour référence future.

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

Ancienne question, mais voici mon avis:

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 utiliser un proxy avec:

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

Remarque: pour les langues qui prennent en charge, cela peut être récursif de queue.

En supposant que la factorsfonction renvoie les facteurs de n (par exemple, factors(60)retourne 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. Cela semble stupide mais fonctionne bien ... et j'essayais de trouver tous les diviseurs appropriés, donc la boucle a commencé à partir de 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 la compréhension de liste et que rien d'autre ne compte pour vous!

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)

Si votre PC a des tonnes de mémoire, une seule ligne brute peut être assez rapide avec 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])

Prend moins de 1s sur mon PC lent.

Ma solution via la fonction générateur est:

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

Pour moi, cela fonctionne bien et est également 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 retourne les diviseurs ligne par ligne comme vous le souhaitez, vous pouvez également faire list.append (n) et list.append (nombre) si vous le souhaitez vraiment