Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Programmation
- » Problème avec un programme Python
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- Ernst
- 03-09-2025 14:33:42
Explications :
Normalement, le programme teste tous les exposants de tous les nombres premiers jusqu’à dépassement. Pour 10^50 il n’y en avait besoin que de 28, et aucun exposant ne dépassait 10.
Pour aller plus loin, il faut à la fois augmenter le nombre de facteurs premiers et la valeur des exposants, toutes choses qui rendent la recherche vraiment chronophage. L’idée a donc été d’une part de déterminer le nombre de facteurs premiers nécessaires, 48, et d’autre part de repérer l’exposant max pour chaque facteur : 13, 8, 4, 4, 3, 2, 2, 2, 2
Cela veut dire que jamais on n’a besoin de plus de $2^{13}$, de $3^{8}$, de $5^{4}$, etc. Au delà des neuf premiers termes tous les autres sont les nombres premiers eux-mêmes. Inutile de préciser que l’élagage est alors optimal, on ne fait que les combinaisons susceptibles de faire un record, on élimine dès que le résultat dépasse N, très efficace.
(par contre déterminer précisément ces valeurs m’a quand même pris un sacré bout de temps ;-)
- Ernst
- 03-09-2025 13:53:37
Bonjour,
On en était donc à un programme qui doit trouver, dans un intervalle donné, l’entier ayant le plus grand nombre de diviseurs.
Grâce à un élagage bien plus efficace de l’arbre de recherche, voici maintenant un programme en Python de base, donc sans bibliothèque externe, qui cette fois obtient le bon résultat sur une plage de 1 à 10^100 en quelques dixièmes de secondes.
import time
PRIMES = [
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223
]
EXP_LIMITS = [13, 8, 4, 4, 3, 2, 2, 2, 2]
MAX_EXP_COUNT = len(EXP_LIMITS)
MAX_PRIME_INDEX = len(PRIMES)
MAX_LIMIT = 10**100 - 1
best_n, best_divs = 1, 1
def parse_limit(text: str):
t = text.strip()
if not t:
return MAX_LIMIT
if t.lower() == 'q':
return None
try:
if "^" in t:
a, b = t.split("^")
return min(int(a) ** int(b), MAX_LIMIT)
return min(int(t), MAX_LIMIT)
except Exception:
return "invalid"
def explore(idx, last_exp, n, divs, used_exps, Nmax):
global best_n, best_divs
if n > Nmax: return
if divs > best_divs or (divs == best_divs and n < best_n):
best_n, best_divs = n, divs
if idx >= MAX_PRIME_INDEX: return
limit = min(last_exp, EXP_LIMITS[idx] if idx < len(EXP_LIMITS) else 1)
p = PRIMES[idx]
powp = 1
for e in range(1, limit+1):
powp *= p
if n * powp > Nmax: break
new_used = used_exps + (1 if e > 1 else 0)
if new_used > MAX_EXP_COUNT: break
explore(idx+1, e, n*powp, divs*(e+1), new_used, Nmax)
# --- Boucle interactive ---
while True:
print("entier, a^b, vide=10^100-1, q pour quitter")
N_input = input("N : ")
if N_input.lower() == 'q':
print("Fin du programme.")
break
Nmax = parse_limit(N_input)
if Nmax == "invalid":
print("❌ Entrée invalide, recommencez.")
continue
if Nmax is None:
print("Fin du programme.")
break
best_n, best_divs = 1, 1
t0 = time.time()
explore(0, 60, 1, 1, 0, Nmax)
t1 = time.time()
print(" ")
print(f"N = {Nmax}")
print(f"Record : {best_n}")
print(f"Nombre de diviseurs : {best_divs}")
print(f"Temps : {t1 - t0:.3f} s")
print(" ")
Toujours plus, telle est ma devise.
- LEG
- 30-08-2025 16:14:22
Bonjour
N = 100000000000000000000000000000000000000000000000011
Record : 87123163749385631861110543148208953735435014848000 avec 18 119 393 280 diviseurs
Temps : 0.8617 s
Bonne soirée
- Ernst
- 29-08-2025 21:39:05
Explications : en fait ici, on ne va plus chercher les records, on va les créer grâce à une formule multiplicative. Si $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$ est la factorisation en nombres premiers de $n$, alors le nombre de diviseurs est donné par $\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$. La recherche de records revient cette fois à explorer des combinaisons d'exposants $(a_1,a_2,\dots,a_k)$. La contrainte $a_1 \ge a_2 \ge a_3 \ge \dots \ge a_k \ge 1$ évite les doublons et ne considére que les factorisations pertinentes.
L'algorithme est implémenté de façon récursive :
- On part de $n=1$, $\tau(1)=1$.
- À chaque étape, on choisit un nouveau premier $p_i$ et un exposant $e$.
- Les contraintes sont :
1. $e \le e_{\text{précédent}}$ (monotonicité)
2. $n \cdot p_i^e \le N$ (ne pas dépasser la borne)
- On calcule $\tau(n)$ immédiatement et on stocke le couple $(n,\tau(n))$.
- On poursuit récursivement jusqu'à ce qu'aucune extension ne soit possible.
Sélection des records
- On garde en mémoire le meilleur $\tau(n)$ rencontré.
- Si $\tau(n) > \text{record}_{\text{courant}}$, on met à jour le record et la liste des nombres.
- Si $\tau(n) = \text{record}_{\text{courant}}$, on ajoute $n$ à la liste des ex aequo.
- À la fin, on obtient tous les nombres $n \le N$ qui battent un record de diviseurs.
Contrairement à la méthode naïve $O(N\sqrt{N})$ ou au crible $O(N \log N)$, le coût dépend uniquement du nombre de combinaisons d'exposants explorées. Pour $N=10^6$, quelques milliers de combinaisons, et même pour $N=10^{50}$ le programme en Python de base met moins de deux secondes.
Tadaa !
- Ernst
- 29-08-2025 20:32:49
Amis de la programmation, bonsoir.
Pour mémoire, il s’agit de trouver le(s) nombre(s) ayant le maximum de diviseurs dans une tranche donnée de 1 à N avec un programme en Python.
Première approche, on essaie tous les diviseurs sur tous les nombres de la plage. Bon, c’est pas mal, en Python cela permet de couvrir plus de 10 000 nombres en quelques secondes.
Ceci dit, ça plafonne quand même assez vite. Pour gagner du temps, on peut considérer qu’au-delà de la racine carrée du nombre on obtient des valeurs déjà trouvées, et on peut donc s’arrêter à celle-ci. Grâce à cela, Python permet maintenant de dépasser les 100 000 nombres sans problème particulier.
Le système s’avère efficace pour les petites valeurs, mais au-delà de quelques centaines de milliers les temps deviennent de plus en plus prohibitifs. Comment faire mieux ?
La solution est plutôt inattendue : un simple crible. L’idée va être d’ajouter systématiquement comme diviseur celui que l’on teste à tous ses multiples. Au départ on a l’impression de calculs dissuasifs, mais c’est tout l’inverse qui se produit : en fait on élimine l’ensemble des tests et de toutes les tentatives inutiles, on n’utilise que l’addition, ce qui permet de dépasser le million en quelques secondes.
Eh bien de façon tout à fait étonnante, on peut faire nettement mieux. Et quand je dis nettement, c’est même invraisemblable. Terminé, game over, réponse instantanée :
import time
# --- Config ---
primes = [
2,3,5,7,11,13,17,19,23,29,
31,37,41,43,47,53,59,61,67,71,
73,79,83,89,97,101,103,107
]
MAX_EXP = 10
# --- Génération récursive ---
def generate_all(limit):
result = []
def dfs(idx, num, divs, prev_exp):
if idx >= len(primes):
return
p = primes[idx]
pow_p = 1
for e in range(1, min(prev_exp, MAX_EXP)+1):
pow_p *= p
next_num = num * pow_p
if next_num > limit:
break
next_divs = divs * (e+1)
result.append((next_num, next_divs))
dfs(idx+1, next_num, next_divs, e)
dfs(0, 1, 1, MAX_EXP)
return result
# --- Lecture de l'entrée ---
def parse_limit(text):
text = text.strip()
if not text:
return 10**6
if '^' in text:
base, exp = text.split('^')
return int(base)**int(exp)
return int(text)
# --- Main ---
if __name__ == "__main__":
N_text = input("Limite N (max 10^51 - 1) : ").strip()
limit = parse_limit(N_text)
if limit > 10**51-1:
raise ValueError("Limite max : 10^51-1")
t0 = time.perf_counter()
numbers = generate_all(limit)
numbers.sort(key=lambda x: x[0])
# --- Extraction des records ---
best_divs = 1
records_list = []
for n, divs in numbers:
if divs > best_divs:
best_divs = divs
records_list = [n]
elif divs == best_divs:
records_list.append(n)
t1 = time.perf_counter()
main_record = records_list[0]
print(f"N = {limit}")
print(f"Record : {main_record} avec {best_divs} diviseurs")
if len(records_list) > 1:
print(f"(même nombre de diviseurs pour {len(records_list)} entiers)")
print(f"Liste complète : {records_list}")
print(f"Temps : {t1-t0:.4f} s")
(j’ai limité à 999999999999999999999999999999999999999999999999999 parce qu’il faut bien s’arrêter quelque part)
Pour les curieux :
https://sites.google.com/view/ernst01/records
- Rescassol
- 29-08-2025 20:00:44
Bonsoir,
Pour trier, il existe sort dans numpy.
Cordialement,
Rescassol
- yoshi
- 29-08-2025 16:45:28
Re,
Ca y est j'ai fini :
pas de pb de fonctionnement...
Ma version d'hier : 68 s puir 100000
Celle d'aujourd'hui 4,28 s : j'ai divisé mon temps par quasiment 16...
Voilà ma version :
from math import sqrt
from operator import itemgetter
from time import time
def Nb_diviseurs(n):
fin=int(sqrt(n))
A=[x for x in range(2,fin+1)]
M=[i for i in A if n%i!=0]
A=list(set(A)-set(M))
qt=2
for x in A:
qt+=1+((x*x)<n)
return qt
def Tri_des_reponses(K):
K=sorted(K,key=itemgetter(1),reverse=True)
(a,b)=K[0]
b0,i=b,0
Rep=[]
while b0==b:
Rep.append(K[i])
i+=1
a,b=K[i]
return Rep
td=time()
lim=100000
L=[(n,Nb_diviseurs(n)) for n in range(2,lim+1)]
R=Tri_des_reponses(L)
print()
lg=len(R)
print("Il y a", lg, "nombre"+"s"*(lg>1), "avec le maximum de diviseurs entre 2 et",lim,":")
for(a,b) in R:
print (" ",a,"possède",b,"diviseurs")
print("Temps écoulé :",round(time()-td,2),"s")
Sortie pour lim= 100000 :
Il y a 2 nombres avec le maximum de diviseurs entre 2 et 100000 :
83160 possède 128 diviseurs
98280 possède 128 diviseurs
Temps écoulé : 4.28 s
Explications
Soit un nombre lim.
Un nombre n, compris entre 1 et lim sera l'argument passé à la première def, comme index d'une boucle for entre 1 et lim+1...
Je considérais cette première def comme la clé de voûte du script et dont j'ai revu l'algo...
Mettons pour lim = 10 000, je cherche la partie entière de 10000 à laquelle j'ajoute 1 --> fin =101
Et je cherche la liste, appelée A, de tous les entiers entre 1 et 100 inclus.
Je calcule la liste de nombres des 1 à 100 non diviseurs de 10000 en partant de 2 et composée des multiples jusqu'à 100 de chaque non diviseur trouvé. Je soustrais la liste M de la liste A.
Pour ce faire, je suis obligé de convertir les liste A et M en Ensembles (avec set()).
le résultat est un ensemble que je suis obligé de reconvertir en liste et je garde le nom A.
A ne contient plus maintenant que des diviseurs de n...
Je traite A qui a réduit et comme chaque nombre de A est un diviseur du n en cours, je n'ai pas de division à faire, juste (en démarrant à qt=2) pour chaque x de A, j'ajoute à qt 1 + (si x*x est inférieur à n) 1.... et je retourne la valeur de qt obtenue.
A l'arrivée, je remplis une liste L avec des tuples, ici des couples (n,qt)...
Lorsque ma liste L est complète, je la trie mais sur le 2e élément de chaque couple : itemgetter(1)...
C'est le job de la 2e def : Tri des diviseurs à qui je passe ma liste L en argument.
Je trie par ordre décroissant des 2e élément de couple via reverse = True (par défaut l'ordre est l'ordre croissant).
Ainsi mes maximums se suivront dès le début de la liste, ce qui permet via test avec while si le 2e élément a changé : là je stoppe et je n'ai plus qu'à retourner la liste des couples résultats...
S'il n'y a qu'un couple résultat je ne mets pas de s à nombre grâce à mon petit jeu de booléen : True c'est 1, False 0 : je rajoute donc "s"*1 soit une fois "s" si le 2e élément est supérieur à 1 et "s"*0 (zéro fois la lettre "s" si lg n'est pas supérieur à 1...
999 et je passe en revue chacun de ces 999 pour trouver les non diviseurs...
A chaque jour suffit sa peine, je reverrai tout ça demain pour gratter encore du temps : la nuit porte conseil : depuis l'époque où j'étais Lycéen, je sais que mon cerveau, en possession du problème, travaille bien mieux tout seul, si je n'interviens plus...
N-B : j'ai pris l'habitude de ne pas importer de modules complets, mais seulement les classes desdits modules dont j'aurai à me servir...
@+
- yoshi
- 29-08-2025 11:30:37
Re,
Je vais regarder...
Mais je veux d'abord finaliser ma dernière version.
Je pense et je dois croire qu'elle sera plus rapide que la précédente...
Mais je pense aussi que la fonction que j'ai remise en cause (nouvel algo) ne pourra pas être aussi rapide que le tien : je n'allais pas recopier bêtement ce que tu avais fait...
En tout, j'aime bien la recherche d'algos.
J'en ai trouvé un il y a 20 ans : j'y avais passé 6 mois...
J'aurais dû déposer un brevet : à ma connaissance, personne n'en a eu l'idée.
J'avais écrit un logiciel de conjugaison française avec mon 1er ordi Amstrad CPC 6128 et son BASIC Locomotive
Il conjugue n'importe quel verbe à n'importe quel temps (existant) de n'importe quel mode (Indicatif, conditionnel...), à la voix active et passive, à la forme pronominale et l'affiche par paquets de 4 temps à l'écran...
De plus, il comporte un module autocorrectif (1 temps à la fois) avec un choix entre 60 verbes les plus courants avec signalement des erreur et affichage de la règle de grammaire en cause (si elle existe).
Je prends en compte les verbes surannés genre apparoir, chaloir, les verbes défectifs (type falloir, pleuvoir...)
J'avais découvert à cette occasion le verbe frire : je fris, tu fris, il frit et pour nous, vous, ils, ça n'existe pas...
Mais mon "tour de force" (6 mois de recherche valent bien que je le qualifie ainsi) : je ne voulais pas que mon soft demande pour les verbes terminés en "ir" : 2e groupe ou 3e groupe. Je voulais qu'il trouve tout seul et sans liste de verbes (difficilement exhaustive)...
Pour un humain, c'est facile :
finir--> finissant 2e groupe
partir --> partant 3e groupe...
Mais comment faire sans liste de verbes en programmation ?
J'ai trouvé un algo : 10/12 lignes et mon soft se débrouille seul sans erreur...
Bon,petit bémol, on pouvait le piéger : il pouvait conjuguer ce qu'il pensait être un verbe. Par exemple : escalier ou bouclier ...^_^
J'avais proposé mon soft à un éditeur qui était emballé : il était prêt à me l'acheter, à condition que je retouche l'affichage des 4 temps lorsque le soft était en mode "autonome"...
J'avais consulté mes collègues profs de Français qui ont partagé mon avis : ce serait dommage et contre-productif...
Alors j'avais répondu : non, tant pis...
Mais j'avais eu un peu de mal à récupérer ma dq : j'avais dû recourir aux menaces.
Aujourd'hui à mes moments perdus (il y en a peu, je travaille à le porter sous Python, j'avais déjà fait le portage de Basic Amstrad vers Turbo Basic de Borland
La recherche d'algo, tu vois, c'est une passion depuis que j'ai découvert la programmation en 1966 et le Plan "Informatique pour tous et que j'ai commencé à bidouiller avec une "Texas TI 66"...
Quant aux remarques de Chat GPT : beaucoup sont intéressantes (très). Je n'ai pas perdu mon temps, ni toi le tien même avec une lecture en diagonale (je prendrai le temps de creuser) : déjà, dans ces conditions, j'entrevois des points auxquels moi, autodidacte, je n'avais pas pensé...
Mais d'abord finaliser aujourd'hui ma dernière version où je change 90% de l'algo que j'avais utilisé : je me suis rendu compte qu'il était trop naïf et peu performant : oui, j'étais largué... 68 s pour recherche de diviseurs entre 2 et 100 000, c'était prohibitif...
Supposons que j'aie 10000 nombres ne se divisant ni pas par 3, 7 et 11.
En éliminant ces tests : j'élimine $\frac 1 3+ \frac 1 7+\frac{1}{11}= \frac{131}{231}des calculs soit environ 57% des calculs, de quoi diviser un temps au moins par 2...
Je maintiens mes propos : je ne fréquente pas les IA.. Et mon esprit est "gauchi" par 37,5 années d'enseignement des Maths, un peu moins pour l'enseignement du Jeu d'Echecs (je piochais dans le jeu, les éléments de stratégie qui, amha, pouvaient servir aux élèves en matière de réflexion... Et pour bien enfoncer le clou, sur mes priorités, si ailleurs les expérimentations officielles sous les auspices de "Sport Études, donc Échecs Études, avec la bénédiction de mon Principal, j'avais baptisé mes classes : Études Échecs...
En outre, j'ai pratiqué le Kendo/Iaido pendant 7/8 ans jusque la municipalité retire les planchers de ses gymnases pour les remplacer par u Terraform (couche plastifiée sur dalle béton)... Oren Kendo, on frappe le sol avec le plat du pied à chaque frappe... Il y avait de quoi se démonter la colonne vertébrale ou avoir régulièrement de douloureuses talonnades...
Notre prof avait donc fermé la boutique.
Comme tu vois, mon mode de pensée est un peu particulier...
Bon, assez parlé de moi...
Ma modif de fonction m'attend : j'ai passé hier ma journée dessus avec 80 % du temps à rectifier des erreurs, de pertes dues à des fausses manipes. Cela a même perturbé ma nuit où je faisais es calculs mentaux au lieu d'essayer de dormir...
@+
- Ernst
- 29-08-2025 08:14:25
Bonjour yoshi,
Content de voir que d’autres partagent mon goût pour la programmation et l’optimisation, pour le plaisir uniquement.
Tu as écrit :
Vouloir progresser en comparant ses programmes avec ce qui serait produit par un programmeur de métier ou une IA serait vouloir monter de niveau […]
et
où il recevrait des conseils, pourrait analyser […] avec un être humain qui serait capable de s'adapter. Toutes choses qu'un professeur virtuel ne serait pas capable de faire
Sur ce point, il est possible que tu ne mesures pas tous les progrès qui ont été faits en la matière. Dès l’introduction du numérique grand public, des chercheurs ont tout fait pour qu’il serve à l’apprentissage, pour le rendre plus convivial, plus didactique aussi, bref pour le mettre au service des apprentissages et non pas pour les remplacer.
Pour te montrer l’état des lieux aujourd’hui, en 2025, et comme tu avais écrit
en matière de temps à 100 000, je suis largué...
Donc je vais tâcher de revoir la recherche des diviseurs.
je me suis permis de demander à une IA (ici ChatGPT en accès libre) de me proposer des améliorations, et surtout de me les expliquer :
https://chatgpt.com/share/68b14dd8-9a4c … b41698d2b8
J’aimerais vraiment avoir ton avis sur ses conseils, parce qu’à mes yeux on est très loin d’un Stockfish capable effectivement de débiter des lignes de jeu hyper pointues, mais sans jamais d’autres explications qu’un score potentiel sorti de ses calculs internes.
- yoshi
- 27-08-2025 12:04:33
Bonjour,
Voilà ma version : elle n'est plus basique à cause de l'appel à itemgetter du module operator...
Mais Pffiou je suis devenu rouillé, j'ai multiplié les fautes de frappe et les fautes de conception.
M'enfin, ouf ! Maintenant ça tourne :
from math import sqrt
from operator import itemgetter
from time import time
def Nb_diviseurs(n):
fin=int(sqrt(n))+1
qt=2
D=[]
for i in range(2,fin):
if n%i==0:
qt+=1
d=n//i
if d!=i:
qt+=1
D.append((n,qt))
return D
def Tri_des_reponses(K):
K=sorted(K,key=itemgetter(1),reverse=True)
Rep,i=[],0
(a,b)=K[0]
b0=b
while b0==b:
Rep.append(K[i])
i+=1
à,b=K[i]
return Rep
td=time()
L,D,lim=[],[],10000
for n in range(2,lim+1):
D=Nb_diviseurs(n)
L=L+D
D=[]
R=Tri_des_reponses(L)
print()
lg=len(R)
print("Il y a", lg, "nombre"+"s"*(lg>1), "avec le maximum de diviseurs entre 2 et",lim,":")
for(a,b) in R:
print (" ",a,"possède",b,"diviseurs")
print("Temps écoulé :",round(time()-td,2),"s")
Et en sortie pour 10000, j'obtiens :
Il y a 2 nombres entre 2 et 10000 avec le maximum de diviseurs entre 2 et 10000 :
7560 possède 64 diviseurs
9240 possède 64 diviseurs
Temps écoulé : 0.46 s
Jusqu'à 10 000 je tiens le choc en matière de temps à 100 000, je suis largué...
Donc je vais tâcher de revoir la recherche des diviseurs.
@+
- Ernst
- 27-08-2025 10:28:22
N = 15000000
Record : 14414400 avec 504 diviseurs
Liste complète : [14414400]
Temps : 0.95 s (multi-workers par plages) plus rapide
Bonjour,
En fait les 15 millions en 1.47 s c'était avec le programme C sur un seul thread. Avec Javascript multi-threads j'obtiens :
N = 15000000
Record : 14414400 avec 504 diviseurs
Liste complète : [14414400]
Temps : 0.28 s (multi-workers par plages)
De façon étonnante, en C avec multi-threading je ne gagne plus rien, c’est dire si Javascript est maintenant optimisé pour certaines opérations, et l'avantage du html, c'est que le programme peut tourner sur n'importe quel navigateur de façon sécurisée.
(50 millions ≃ 3 s sur mon PC, 8 s sur mon smartphone et 19 s sur ma tablette)
- LEG
- 27-08-2025 07:39:46
bonjour
pour :
N = 15000000
Record : 14414400 avec 504 diviseurs
Liste complète : [14414400]
Temps : 0.95 s (multi-workers par plages) plus rapide
Mais pour ;
N = 30000000
Record : 21621600 avec 576 diviseurs
(même nombre de diviseurs pour 5 entiers)
Liste complète : [21621600, 24504480, 27387360, 28274400, 28828800]
Temps : 2.53 s (multi-workers par plages) plus lent ....
- Ernst
- 26-08-2025 14:00:17
Bonjour,
Juste pour le fun, je me suis amusé à faire un programme en C pour obtenir la même chose, sur mon ordinateur c'est cette fois quinze millions en moins de deux secondes :
N = 15000000
Record : 14414400 avec 504 diviseurs
Liste complète : [14414400]
Temps : 1.47 s
Encore mieux, Javascript et parallélisme (PC multicœur), plutôt pas mal, trente millions en moins de deux secondes :
N = 30000000
Record : 21621600 avec 576 diviseurs
(même nombre de diviseurs pour 5 entiers)
Liste complète : [21621600, 24504480, 27387360, 28274400, 28828800]
Temps : 1.39 s (multi-workers par plages)
Puisque cela dépend beaucoup du matériel, chacun pourra se faire une idée avec le sien :
https://sites.google.com/view/ernst01/crible_1
Bref, on voit que :
- l’algorithme fait une différence
- le langage fait une différence
- le matériel fait une différence
- yoshi
- 25-08-2025 17:30:13
[EDIT]
J'ai été pris de vitesse par BlackJack et Ernst. Pô grave. mais désolé, il pourrait donc y avoir du déjà vu.
J'ai perdu beaucoup de temps aujourd'hui.
Je programme à ma façon : ce n'est pas aujourd'hui que je vais changer...
Bonjour,
Vouloir progresser en comparant ses programmes avec ce qui serait produit par un programmeur de métier ou une IA serait vouloir monter de niveau aux Echecs en luttant contre une machine...
Je sais de quoi je parle : j'ai formé des générations d'élèves parallèlement à mes cours de maths, j'ai encore un niveau 2e catégorie (>1800 Elo) et je ne peux plus lutter contre le programme stockfish qui tourne sur mon PC, même réglé à bas niveau.
Un certain nombre de parents me demandaient conseil sur le type de machine spécialisée à acheter pour leur enfant comme cadeau de Noël : je répondais invariablement, de ne rien acheter, mais de plutôt l'inscrire dans un club où il recevrait des conseils, pourrait analyser ses partes avec un être humain qui serait capable de s'adapter. Toutes choses qu'un professeur virtuel ne serait pas capable de faire....
Revenons à nos moutons. Cortes, tu commences à programmer en autodidacte, c'est bien.
Alors, pense bien que la route est longue et que tu pourrais te décourager devant les inévitables plantages.
Il ne faut pas, il faut te mettre dans la tête qu'il n'est pas anormal qu'un programme ne fonctionne pas du premier coup...
Heureusement, un langage de programmation s'il est bête, est particulièrement rapide, calcule juste et surtout, il est discipliné et obéissant : il fait très exactement ce que tu lui demandes de faire, ni plus, ni moins...
Ton programme est en erreur. D'accord ! Comment savoir où et pourquoi ?
As-tu une idée claire de ce que chaque fonction que tu as créée est censée produire ?
Si oui, es-tu certain que chacune fait bien ce que tu attendais d'elle ?
Pour le savoir, on conseille généralement aux débutants de faire des essais et de poser des "mouchards"...
Par exemple, ici dans le morceau mort.
Python passe-t-il par là ?
Liste = []
for i in range(1, 1001):
m = nombre_de_diviseurs(i)
Liste.append(m)
r = max(Liste)
return r
# Ici tu peux coller un mouchard genre : print ("Coucou, je suis sorti de la fonction")
Liste_1000 = range(1,1001)
entier_cherché = [x for x in Liste_1000]
if diviseurs(x)==r:
return entier_cherché
Et tu t'apercevrais que non, Python ne passe pas par là...
Sais-tu,"à la main", rechercher la lises des diviseurs d'un nombre en économisant le travail ?
Sur deux lignes.
Exemple 1 :
$\mathcal{D}(48)= ?$
48 se divise : par 1 et donc par 18/1 = 48, par 2 et dpnc par 48/2 = 24, par 3 et donc par 48 /3 = 16. etc. on écrit au fur et à mesure :
1 2 3 4 6
48 24 16 12 8
On arrête là... Pourquoi ? Parce que l'étape suivante conduirait à écrire 8 et 6 en dessous (déjà trouvés)....
On lit alors la première ligne de G à D, à la fin on descend sur la ligne 2 et on reprend la lecture de D à G, ce qui donne :
$\mathcal{D}(48)= \{1,\, 2,\ 3,\, 4,\ 6,\, 8,\, 12,\, 16,\, 24,\, 48\} $
EXemple 2
$\mathcal{D}(120)= ?$
1 2 3 4 5 6 8 10
120 60 40 30 24 20 15 12
D'où
$\mathcal{D}(120)= \{1,\, 2,\ 3,\, 4,\ 5,\, 6,\, 8,\, 10,\, 12,\, 15,\,20,\,24,\,30,\,40,\,60,\,120\} $
Pour un humain, il est évident qu'on s'arrête après 10 12, mais comment le faire trouver par Python ?
1. Q : Qu'est-ce qu'on cherche en fait ?
R : On cherche le nombre compris entre 1 et 1000 qui a le grand nombre de diviseurs
2. Python peut-il trouver qu'il doit stopper les recherches après 6 (pour 48) ou après 10 (pour 120) ?
R : Un langage de programmation calcule très bien : il fait qu'il ait un test d'arrêt, un nombre compris entre 6 et 8 ou 10 et 12
3. Q : Oui, d'accord : 7 et 11. Mais pour 144 par exemple, il n'y a d'entier entre 12 et 12 ($144 = 12\times 12$) ... Alors ?
R : $144 =12\times 12 =12^2$ et coucou les maths de 3e : $12=\sqrt{144}$
4. Q : Oui, mais $\sqrt{48}\approx 6.92$... et $\sqrt{120}\approx 10.95...$ ne sont pas des entiers ! On fait quoi ?
R : On prend la parue entière des racines,soit 6 et 10 et on ajoute 1...
Reste le cas des racines carrées exactes... Soit on fait un test, soit on passe outre et on fait comme s'il y avait systématiquement un doublon à éliminer dans la liste (mais là, ce n'est plus du "basique"...
Exemple
L=[1,2,2,3,4,1,3]
L= list(set(L))
print (L)
Et on obtient : [1, 2, 3, 4]. Je ferais plus basique dans ma vers
La méthode est rapide et automatique L=list(set(L)) : l'instruction set() transforme la liste L en un ensemble puis supprime les doublons et le list() rétablit une liste.
Petit bémol : on n'est pas sûr de conserver l'ordre des éléments.
Je ferai plus basique dans ma version définitive....
5. Ici, y a-t-il un intérêt à classer les diviseurs par ordre croissant et à garder l'ordre ?
R: Non, puisqu'on veut le nombre d'éléments de la liste. On peut donc stocker les diviseurs dans une liste par 2 à la fois :
$L= [1,\,120,\,2,\,60,\,3,\,40,\,4,\,30,\,5,\,24,\,6,\,20,\,8,\,15,\,10,\,12]$...
Je continue demain...
@+
- Ernst
- 25-08-2025 14:50:10
Bonjour,
Le problème posé est plutôt intéressant pour aborder les enjeux de la programmation. J’utilise Basthon pour avoir une base identique à tous mes programmes, et conserver un code sans bibliothèque externe.
Première mouture, le test de tous les diviseurs possibles pour chaque nombre :
import time
def diviseurs(n):
d = []
for i in range(1, n + 1):
if n % i == 0:
d.append(i)
return d
def records(N):
max_div = 0
records = []
for n in range(1, N + 1):
nb = len(diviseurs(n))
if nb > max_div:
max_div = nb
records = [n]
elif nb == max_div:
records.append(n)
return max_div, records
N = 10_000 # méthode brute limitée
start = time.perf_counter()
max_div, recs = records(N)
end = time.perf_counter()
print(f"N = {N}")
print(f"Record : {recs[0]} avec {max_div} diviseurs")
if len(recs) > 1:
print(f"(même nombre de diviseurs pour {len(recs)} entiers)")
print(f"Liste complète : {recs}")
print(f"Temps : {end - start:.2f} s")
Résultat :
N = 10000
Record : 7560 avec 64 diviseurs
(même nombre de diviseurs pour 2 entiers)
Liste complète : [7560, 9240]
Temps : 3.91 s
On peut faire mieux en constatant qu’à chaque fois qu’on a un diviseur, on a aussi un résultat. Cela permet de s’arrêter à la racine carrée et donc de pouvoir aller environ dix fois plus loin dans un temps raisonnable :
import time, math
def diviseurs(n):
d = []
limite = int(math.isqrt(n))
for i in range(1, limite + 1):
if n % i == 0:
d.append(i)
autre = n // i
if autre != i:
d.append(autre)
return d
def records(N):
max_div = 0
records = []
for n in range(1, N + 1):
nb = len(diviseurs(n))
if nb > max_div:
max_div = nb
records = [n]
elif nb == max_div:
records.append(n)
return max_div, records
N = 100_000
start = time.perf_counter()
max_div, recs = records(N)
end = time.perf_counter()
print(f"N = {N}")
print(f"Record : {recs[0]} avec {max_div} diviseurs")
if len(recs) > 1:
print(f"(même nombre de diviseurs pour {len(recs)} entiers)")
print(f"Liste complète : {recs}")
print(f"Temps : {end - start:.2f} s")
Résultat :
N = 100000
Record : 83160 avec 128 diviseurs
(même nombre de diviseurs pour 2 entiers)
Liste complète : [83160, 98280]
Temps : 1.17 s
Peut-on encore faire mieux ? Oui, nettement, en partant du principe que chaque multiple d’un diviseur est donc divisé par ce diviseur. Autrement dit si on considère 3, eh bien on peut le rajouter comme diviseur à 3, 6, 9, 12, …. Avantage, on ne fait ni test, ni division, ni modulo, on n’a plus que des incrémentations :
import time
def records(N):
div_count = [0] * (N + 1)
for i in range(1, N + 1):
for j in range(i, N + 1, i):
div_count[j] += 1
max_div = max(div_count)
records = [i for i, nb in enumerate(div_count) if nb == max_div]
return max_div, records
N = 1_000_000
start = time.perf_counter()
max_div, recs = records(N)
end = time.perf_counter()
print(f"N = {N}")
print(f"Record : {recs[0]} avec {max_div} diviseurs")
if len(recs) > 1:
print(f"(même nombre de diviseurs pour {len(recs)} entiers)")
print(f"Liste complète : {recs}")
print(f"Temps : {end - start:.2f} s")
Résultat :
N = 1000000
Record : 720720 avec 240 diviseurs
(même nombre de diviseurs pour 5 entiers)
Liste complète : [720720, 831600, 942480, 982800, 997920]
Temps : 1.34 s
Calcul en Python de base de tous les diviseurs d’un million de nombres en moins de deux secondes, qui dit mieux ?