Nombre Composé
Bonjour,
j'ai un problème pour continuer l'Algorithme qui décompose un nombre en facteur premier. J'aimerais avoir votre aide SVP, merci d'avance pour votre bienveillance.
voila l'algorithme:
programme nombre_composé
variables nbr, cont,
début
lire (nbr)
pour cont ? 1 à nbr
si (nbr modulo cont) = 0 Alors
..............
finsi
finpour
j'ai un problème pour continuer l'Algorithme qui décompose un nombre en facteur premier. J'aimerais avoir votre aide SVP, merci d'avance pour votre bienveillance.
voila l'algorithme:
programme nombre_composé
variables nbr, cont,
début
lire (nbr)
pour cont ? 1 à nbr
si (nbr modulo cont) = 0 Alors
..............
finsi
finpour
8 réponses
-
Bonsoir Gradi,
Sans énoncé correct .. difficile de donner un coup de main.
En plus, il faut prendre l'habitude
- d'écrire les mots-clés en majuscule: SI, FIN SI, TANT QUE, etc
- Indenter le programme, même l'algo
- Penser à utiliser la balise "Code" .. elle est faite pour ca -
L'énoncer d'écrire un algorithme qui demande à l'utilisateur d'entrer un nombre entier et l'algorithme lui fournira la décomposition du nombre eb facteur premier
-
-
-
-
ModérateurPour moi un "algorithme qui décompose un nombre en facteur premier" c'est très explicite, c'est de l'algèbre niveau terminale (je ne sais pas si tu en es là)
Il faut trouver la série de nombres premiers dont le produit donne l'entier cherché.
Si je reprends mes exemples :
12 se décompose en [2,2,3] car 12=2*2*3 avec 2 et 3 qui sont premiers.
17 se décompose en [17] car 17=17 avec 17 qui est premier.
30 se décompose en [2,3,5] car 30=2*3*5 avec 2,3 et 5 qui sont premiers.
Quelques propriétés :
La décomposition en nombre premier est unique (à l'ordre près)
Un même nombre premier peut être utilisé plusieurs fois dans une même décomposition. -
-
-
Gradi,
Dans ton alogo, il faut déclarer le variables, les initialiser (évidemment), puis,
il faut:
soit stocker les nombres premier .. à éviter car toute une ribambelle,
soit faire tourner une boucle incrémentale et vérifier à chaque nombre s'il peut diviser le nombre X (ce nombre étant celui entré par l'utilisateur)
Résultat possible = 2
1) X n'est divisible que par un et par lui-même .. alors il est premier et tu l'affiche tel quel
2) X est divisible par plusieurs autre nombres .. alors tu refais une boucle en "lisant" les nombres premiers de la première boucle et en commençant par le plus petit (sinon ce serait trop facile !).
a chaque fois, il faut re-mémoriser le nouveau X, c'est-à-dire le X que tu vient de diviser par ce nombre premier et recommencer la boucle au début du tableau.-
ModérateurÇa semble un peu compliqué tout ça, en particulier la partie "recommencer la boucle au début du tableau."
De quel tableau tu parles ? De plus il n'est pas nécessaire de recommencer au début.
Si tu as déjà testé que X n'était pas divisible par P, alors X/Q ne sera pas non plus divisible par P. -
-
ModérateurEn Java ça donnerait ça :
// version O(n) public static void decomposer(int n) { for (int d=2; d<=n; d++) { while (n%d==0) { System.out.println(d); n/=d; } } }//version O(sqrt(n)/2) public static void decomposer(int n) { while (n%2==0) { System.out.println(2); n/=2; } for (int d=3, max=(int) Math.sqrt(n); d<=max; d+=2) { while (n%d==0) { System.out.println(d); n/=d; max=(int) Math.sqrt(n); } } if (n!=1) System.out.println(n); } -
-
ModérateurNon, j'ai supprimé l'option MP, mais au besoin j'ai laissé la discussion que j'ai créé l'autre jour et que tu peux continuer (même si ça n'a rien à voir)
Le System.out.println(2); est correct, puisque c'est uniquement sur la boucle while (n%2==0) où je traite tous les nombres pairs (ce qui permet de faire d+=2 dans le for, au lieu de d++)
-
-
Regarder d'abord ce que j'ai pu trouver:
PROGRAMME Nombre_Composé
VAR k, nbre : ENTIER
VAR dec : CHAINE DE CARACTERES
DEBUT
POUR i allant de 2 à nbre
test = (nbre modulo k)
SI test = 0 ALORS
dec = test & " * "
FINSI
FINPOUR
dec = DELETE ( dec, LONG(dec), *) ( pour supprimer le * terminal )
AFFICHER " Le nombre décomposé en facteur premier est alors:", dec
FIN
Ai-je raison de faire comme ça? -
Bonsoir Gradi,
SI test = 0 ALORS dec = test & " * " FINSI
Dans ce code test vaut 0 .. donc la phrase finale va être du genre:
"Le nombre décomposé en facteur premier est alors: 0 * 0 * 0 * 0 * 0"
En plus pour comparer deux variables c'est "==" et pas "="
Edit: en gras pour visu -
Voyez un peu l'Algorithme corrigé
PROGRAMME Nombre_Composé
VAR k, nbre : ENTIER
VAR dec : CHAINE DE CARACTERES
DEBUT
POUR i allant de 2 à nbre
test = (nbre modulo k)
SI test == 0 ALORS
dec = k & " * "
FINSI
FINPOUR
dec = DELETE ( dec, LONG(dec), *) ( pour supprimer le * terminal )
AFFICHER " Le nombre décomposé en facteur premier est alors:", dec
FIN
Est-ce maintenant correct?-
- Les variables "k" et "dec" doivent être initialisée, sinon, on pourrait avoir des surprises de mauvais goût !
- Avec ce code "dec = k & " * " ", "dec est à chaque fois réinitialisé .. il faut faire "dec = dec + k & " * " " pour ajouter en fin de chaîne
- Je pense que tu n'as pas saisi le fonctionnement du problème. Regarde ce qu'à écrit KX ici : https://forums.commentcamarche.net/forum/affich-26723985-nombre-compose#7
Cela te permettra de comprendre comment procéder.
-
-
Pour le problème de k, je devais plutôt écrire i, le k est apparu bizarrement, c'est le lapsus scriptae; pour le dec, j'ai suivi ton conseil Vois maintenant ce qui suit:
PROGRAMME Nombre_Composé
VAR k, nbre : ENTIER
VAR dec : CHAINE DE CARACTERES
DEBUT
dec = ""
POUR i allant de 2 à nbre
test = (nbre modulo i)
SI test == 0 ALORS
dec = dec + i & " * "
FINSI
FINPOUR
dec = DELETE ( dec, LONG(dec), *) ( pour supprimer le * terminal )
AFFICHER " Le nombre décomposé en facteur premier est alors:", dec
FIN -
Bonjour Gradi,
Tu peux remplacertest = (nbre modulo i) SI test == 0 ALORS
parIf (nbre MODULO i == 0) Then
On est pas obligé de le mémoriser!
Quand tu passe dans la condition "SI" il faut décrémenter i de 1, car il faut recommencer avec le même diviseur .. ce n'est pas parce qu'un nombre (600) est divisible par 2 une fois, qu'il n'est plus divisible par 2 .. une deuxième fois .. une troisième fois, etc.
Ceci "dec = DELETE ( dec, LONG(dec), *) ( pour supprimer le * terminal ) " n'est pas propre !
Il faut ajouter une variable booléenne 'DeJaPasse' et l'initialiser à 'FAUX' .. dans la condition si, tu la modifie en 'VRAI' après avoir modifié la variable 'dec'.
Et dans la condition 'SI', tu affiche comme ceci:SI(DeJaPasse)ALORS dec = dec + " * " + i SINON dec = dec + i FIN SI
De cette façon, il ne faut plus "chipoter" à la variable-
ModérateurJe ne comprends pas trop les algorithmes écrits comme ça, mais il me semble qu'il y a un autre problème, c'est que nbre ne change jamais.
Or puisque l'on compte plusieurs fois le même diviseur, il ne faudrait pas voir à faire une boucle infinie en faisant toujours le même test :
2 divise 600, donc on recommence avec 2 2 divise 600, donc on recommence avec 2 2 divise 600, donc on recommence avec 2 2 divise 600, donc on recommence avec 2 etc.
En réalité il faudrait faire :
2 divise 600, donc on recommence avec 2 et 300 2 divise 300, donc on recommence avec 2 et 150 2 divise 150, donc on recommence avec 2 et 75 2 ne divise pas 75, donc on recommence avec 3 et 75 etc.
-
Bonjour KX, Gradi,
Je suis heureux de voir que l'on peut toujours compter sur ta vigilance.
Il y a tellement à faire que je n'ai pas vu cette variable 'nbre' qui ne varie pas.
Effectivement, KX a raison .. quand tu as défini que nbre modulo 2 = 0 il faut alors diviser n par ce nombre ! c'est impératif !
Merci KX.
-
