Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#1 05-12-2016 13:23:30
- justro
- Membre
- Inscription : 17-11-2016
- Messages : 1
algorithme
slt la famille
Salut la famille
pouvez vous m'aider a écrire un algo qui étant donne le nombre affiche sa décomposition en produit de facteurs premier ex:20=2^2×5;100=2^2×5^2.
merci a l'avance
Dernière modification par yoshi (05-12-2016 13:32:32)
Hors ligne
#2 05-12-2016 15:30:50
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 035
Re : algorithme
Bonjour,
De façon très informelle, voici un algorithme. On prend un entier $n$.
On initialise $k$ à $2$ et on fait augmenter $k$ tant que $k\leq n$ et que $k$ ne divise pas $n$.
Si on sort de cette boucle avec $k<n$, alors $k$ est le plus petit diviseur premier de $n$, on l'ajoute à la liste
des diviseurs premiers de $n$, et on recommence avec $n/k$. Si $k=n$, alors $n$ est premier.
Par exemple, si tu pars de 20, tu feras les itérations suivantes :
* 2 divise 20, c'est donc un diviseur premier de 20, on l'ajoute à la liste et on repart de 20/2=10
* 2 divise 10, on l'ajoute à la liste et on recommence avec 5.
* 2,3,4 ne divisent pas 5. 5 est donc premier, on l'ajoute à la liste et on arrête.
La liste des diviseurs premiers de 20 est donc {2,2,5}. On tient bien compte de la multiplicité.
F.
En ligne
#3 05-12-2016 18:23:30
- yoshi
- Modo Ferox
- Inscription : 20-11-2005
- Messages : 16 948
Re : algorithme
Salut gamin,
Bienvenue dans la famille...
Que fait-on à la main ?
On prend 2. <----------------------------------------------------------------------------------------------|
|--> nombre est il multiple de 2 ? |
OUI on prend le quotient de nombre par 2. On remplace nombre par le quotient --|
| --- NON
On prend 3. <----------------------------------------------------------------------------------------------|
|--> nombre est il multiple de 3 ? |
OUI on prend le quotient de nombre par 2. On remplace nombre par le quotient --|
| --- NON
...........
Et ainsi de suite.
Condition(s) d'arrêt
- nombre = 1
- quotient > racine
Je l'ai fait fait en Python, je peux le modifier pour AlgoBox...
Quelques exemples de sortie :
>>> decompo(1921)
1921 = 17 x 113
>>> decompo(6870)
6870 = 2 x 3 x 5 x 229
>>> decompo(7825)
7825 = 5^2 x 313
>>> decompo(8825)
8825 = 5^2 x 353
>>> decompo(8625)
8625 = 3 x 5^3 x 23
@+
Arx Tarpeia Capitoli proxima...
Hors ligne
Pages : 1