Bonjour
Etant donner un nombre N et ses diviseurs:{d1;d2;d3;...dn} dans l'ordre, on écarte 1 et N
Le but est de progrmmer à la calculette les produits à deux diviseurs, à trois diviseurs, etc... qui donnent N
exemple:d6*d5=N; d1*d4*d9=N etc...
Y a t-il un théoreme ou une regle mathématiques ou quelquechose comme ça qui permet de d'arrêter la recherche aux produit à trois diviseurs ou à quatre diviseurs etc...
Ce que je veux dire, trouver les produits à p diviseurs qui dépassent N
Merci pour vos commentaires
Bonjour
Bonjour,
la question est en fait assez mal posée parce que le diviseur 3 et le diviseur 4 ou 6 par exemple ne sont pas "de même nature"
3 est un diviseur premier de 12
4 ou 6 est un diviseur de 12 mais qui n'est pas premier
étalons en ligne tous les diviseurs premiers de N dans un ordre quelconque
supposons qu'il y ait n diviseurs premiers en tout
ainsi 12 possède 2 diviseurs premiers : 2 et 3 mais le 2 est compté deux fois de sorte qu'ici on va considérer les diviseurs premiers 2, 2 et 3 ce qui fait pour mon propos 3 diviseurs premiers.
il y a entre ces trois diviseurs premiers 2 "séparations" et donc 22 = 4 façons de "grouper" ces diviseurs premiers en mettant ou non et indépendamment ces séparations
2*2*3 (je groupe en un seul diviseur qui est 12, aucune séparation)
2 et 2*3 (je groupe en deux diviseurs 2 et 6, la première séparation seule)
2*2 et 3 (je groupe en deux diviseurs 4 et 3, la seconde séparation seule)
2, 2 et 3 (les deux séparations et 3 diviseurs)
choisir un autre ordre pour ranger les diviseurs premiers au départ donnera ou pas des décompositions différentes.
si le nombre N se décompose ainsi en facteurs premiers pi d'exposants ei le nombre totale de facteurs premiers qui sont à considérer dans ce procédé est la somme des exposants de tous ces facteurs premiers
12 = 2231 somme des exposants 2+1, on s'arrêtera à un produit de 3 facteurs
72 = 2332, on s'arrêtera à un produit de 3+2 = 5 facteurs
reste que les diviseurs à choisir ne sont pas n'importe quoi puisque il faut prendre dans le principe énoncé précédemment chaque facteur premier "individuel" une fois et une seule en tout !
dans le cadre de l'exo, on ne sait rien du tout des diviseurs premiers de N, on a juste la liste de ses diviseurs, de sorte que ces considérations sont inutiles de toute façon.
on choisit de toutes les façons possibles 1 seul, 2, 3, 4, 5, etc etc diviseurs de la liste et on teste si le produit est N ou pas
(on rejette ce choix si c'est différent de N, et ce sans état d'ame aucun)
donc ta limite ce sera .. brutalement et sauvagement le nombre de diviseurs de la liste
après que l'on cherche à améliorer cet algorithme par application du principe de choix intelligent des diviseurs premiers pourquoi pas, mais c'est à mon avis aller bien au dela de ce qui est demandé.
salut
si d est un diviseur de n alors n = d * (n/d) donne tous les produits à deux diviseurs de n
il suffit de ne pas prendre d = 1 ou d = n
généralisation : produit de k diviseurs donnant n
on peut supposer les diviseurs de n ranger dans une liste d()
1 :: choisir un diviseur de n d (différent de 1 et n)
2 :: choisir un diviseur de n/d (différent de 1)
3 :: répéter k - 2 fois l'opération 2 ::
4 :: si ça ne marche pas retourner en 1 ::
alors le produit ce ces k nombres donne n ...
le défaut de cette méthode est là :
choisir un diviseur de n/d
on ne dispose pas de cette table des diviseurs de n/d, seulement de la table des diviseurs de n
donc il faut la "fabriquer"
ou alors changer complètement notre fusil d'épaule et ne PAS utiliser la table des diviseurs de N du tout
(elle est donnée, elle n'est pas calculée par l'algorithme !!)
c'est à dire qu'on la calcule elle aussi au fur et à mesure, exactement par le même algorithme utilisé en même temps pour calculer les diviseurs de n/d, récursivement.
à noter toutefois que ce "récursivement" fait qu'il est impossible de savoir quand on va s'arrêter, ni combien de diviseurs on prend et que toutes les boucles imbriquées seront des "tant que"
avec en plus une gestion dynamique d'un tableau listant tous les diviseurs pris au fur et à mesure de leur "choix" et du retour en arrière pour un autre choix d'un diviseur de n/d
(la "pile" de la récursion en fait)
évidemment par rapport à la méthode "bourrin" de choisir brutalement des diviseurs dans la liste donnée et de les multiplier "pour voir", l'algorithme est bien plus efficace, mais au prix d'une complication bien plus grande !!
(ta description planque bien trop de détails pour qu'on puisse en juger, mais réaliser pratiquement ton algorithme fera mettre le doigt sur toute ces histoires de récursion)
certes oui .... c'est très théorique et ça peut cacher des choses ....
considérons que nous ayons la liste des diviseurs (qu'il n'est pas difficile de programmer de toute façon) et qui ne pose aucun pb ...
comme tu l'as remarqué il est important d'avoir les premiers on peut aussi programmer la décomposition d'un entier en produit de facteurs premiers .... on 'arrête à aux premiers < et du moins obtenir ces premiers effectivement ...
en considérant 2 et 3 puis les entiers et leur puissance correspondante (je l'ai fait avec mes spe)
on peut donc au départ avoir ou construire :
la table des diviseurs
la table des facteurs premiers avec leur exposant ...
.... (temps de réflexion)
en fait non je ne vois pas où est le pb :: tout diviseur de n/d est un diviseur de n !!!!
il suffit donc de le choisir dans la table avec la condition < n/d ....
pardon je me suis mal exprimé :
dans la table des diviseurs de n il y a des diviseurs de n/d ... sauf si n/d est premier ...
Bonjour et merci pour vos réponses
J'ai lu un peu vos réponses mais c'est un peu plus théorique pour moi mais je prendrai du temps pour essayer de comprendre.
Vous avez fait allusion à la liste donnée des diviseurs de N, cette liste je l'obtiens facilement par un algorithme un peu "brutal" tout simplement en divisant N par 2, 3 ,4 etc... jusqu'à N/2
Si on peut s'en passer cela n'e présente aucun problème pour moi.
bien sur qu'il faut faire un test pour un diviseur de d/n ... mais ce n'est pas si long .... puisqu'on en cherche dans les diviseurs de n ....
et bien sur je ne voulais pas mettre tous les détails ... seulement le principe ...
mais l'idée est simple et à mon très efficace voire même tout aussi efficace sinon plus qu'avec la décomposition en nombre premier ....
on choisit un diviseur d dans la liste
on choisit un diviseur d' dans la liste distinct de d
on vérifie qu'il divise d/n .... sinon on en choisit un autre ...
et ainsi de suite ...
maintenant pour le choix il y a deux cas : on le fait au hasard ... et ça peut être très long ...
ou on le fait avec de l'ordre ...
Vous devez être membre accéder à ce service...
Pas encore inscrit ?
1 compte par personne, multi-compte interdit !
Ou identifiez-vous :