Bonjour à tous et toutes, J'ai trouvé la décomposition en facteurs premiers d'un nombre assez grand de l'ordre de 2**63. Ce nombre possède 161280 diviseurs. Ce qui me donne la possibilité de comparer plus facilement certains algorithmes pour retrouver la liste des diviseurs de ce nombre. Aucune de mes trois méthodes ne donne une liste triée et je soupçonne que le "désordre" n'est pas tout à fait le même pour ces méthodes. J'ai comparé le temps d'exécution de trois méthodes pour tenter de trouver la meilleure méthode. En général, les méthodes itératives sont très lentes, comme l'illustre ma première méthode, car on évalue chaque diviseur en faisant des produits de puissance. J'ai utilisé une méthode appelée "compteur circulaire" ou "compteur kilométrique" dans laquelle on fait avancer un compteur. La différence est que pour les compteurs "normaux", on avance d'abord les unités de 0 à 9 et on retourne à 0 en avançant les dizaines de un et ainsi de suite. Dans mon cas, j'avance jusqu'à l'exposant maximum compris pour chaque facteur. On pourrait dire que les "roulettes" de mon compteur n'ont pas le même nombre de dents. Ensuite, je calcule la puissance maximale pour chaque facteur une seule fois au début. À chaque itération, je ne fais qu'une multiplication, mais je fais aussi une division chaque fois que je retourne à 0 pour une roulette de mon compteur. Voici ce que mon test donne: - from time import perf_counter from itertools import product from math import prod
def listeProduits(facteurs): facteurs, exposants = zip(*facteurs) for compteur in product(*(range(e+1) for e in exposants)): diviseurs.append(prod(f**e for f, e in zip(facteurs, compteur)))
def listeRecursive(facteurs, produit): f, e = facteurs[0] p = 1 for _ in range(e+1): if len(facteurs) > 1: listeRecursive(facteurs[1:], p * produit) else: diviseurs.append(p * produit) p *= f
def listeIterative(facteurs): maximums = [f**e for f, e in facteurs] facteurs, exposants = zip(*facteurs) n = len(facteurs) compteur = [0] * n nombre = 1 while True: diviseurs.append(nombre) i = 0 while i < n and compteur[i] >= exposants[i]: nombre //= maximums[i] compteur[i] = 0 i += 1 if i >= n: break nombre *= facteurs[i] compteur[i] += 1
if dp != dr or dp != di: print("erreur") - 0.428 secondes 161280 0.095 secondes 161280 0.041 secondes 161280 - Est-ce que quelqu'un aurait un truc pour améliorer l'une de ces trois méthodes pour la rendre plus efficace? Merci pour toute suggestion.
Le Tout est souvent plus grand que la somme de ses parties.
Si ça ne prend que 0.041 s. sur votre machine, quelle durée atteindre pour être plus efficace? Mais peut être que la question ne porte que sur le code et pas le temps de calcul.
Re-bonjour, J'ai trouvé une méthode à la fois plus simple et plus rapide que ma méthode du compteur kilométrique (ou "odomèttre"). On utilise trois boucles imbriquées seulement, et ce, indépendemment du nombre de facteurs ou leurs puissances. La première concerne les facteurs et leur exposant. La seconde concerne toutes les puissances d'un facteur (sauf la puissance 0). La troisième multiplie toutes les valeurs de la sous-liste courante par la puissance courante du facteur courant et l'ajoute à la liste. (ça fait beaucoup de courant ...) La première sous-liste ne contient que le nombre 1. La seconde sous-liste inclus tous les produits par les puissances du premier facteur, et ainsi de suite. Voici ce que ça donne:
from time import perf_counter from itertools import product from math import prod
def listeProduits(facteurs): facteurs, exposants = zip(*facteurs) for compteur in product(*(range(e+1) for e in exposants)): diviseurs.append(prod(f**e for f, e in zip(facteurs, compteur)))
def listeRecursive(facteurs, produit): f, e = facteurs[0] p = 1 for _ in range(e+1): if len(facteurs) > 1: listeRecursive(facteurs[1:], p * produit) else: diviseurs.append(p * produit) p *= f
def listeIterative(facteurs): maximums = [f**e for f, e in facteurs] facteurs, exposants = zip(*facteurs) n = len(facteurs) compteur = [0] * n nombre = 1 while True: diviseurs.append(nombre) i = 0 while i < n and compteur[i] >= exposants[i]: nombre //= maximums[i] compteur[i] = 0 i += 1 if i >= n: break nombre *= facteurs[i] compteur[i] += 1
def listeAdditive(facteurs): diviseurs.append(1) l = 1 for f, e in facteurs: p = f for _ in range(e): for i in range(l): diviseurs.append(diviseurs[i]*p) p *= f l = len(diviseurs)
Le Tout est souvent plus grand que la somme de ses parties.
Liste des diviseurs à partir des facteurs premiers
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.