Dans cet exercice, d’après la deuxième question, il est préférable d’écrire une procédure qui revoie le nombre de diviseurs de l’entier en entrée et un booléen pour vérifier s’il est premier ou non.
1- Fonction Premier(E/ X : entier ):booleen;
Var I,M:entier;
Debut
Si X=1 Alors Premier ← Faux
Sinon M ← X DIV 2 ; I ← 2 ; Premier ← Vrai ;
Tantque I≤M et Premier
Faire
Si X mod I=0 Alors Premier ← Faux Fsi ;
I←I+1 ;
Fait ;
Fsi ;
Fin ;
2- Fonction SemiPremier(E/ X : entier ):booleen;
Var I,M:entier;
Debut
Si Premier(X)
Alors SemiPremier ← Faux
Sinon M ← X DIV 2 ; I ← 2 ; SemiPremier ← Vrai ; Tantque I≤M et SemiPremier Faire
Si X MOD I=0
Alors Si (Non Premier(I))ou(Non Premier(X DIV I))
Alors SemiPremier ← Faux
Fsi
Fsi ;
I←I+1 ;
Fait;
Fsi;
Fin ;
3- Pour cette question, il s’agit de trouver une formule pour générer les nombre de la forme abcabc afin d’optimiser l’algorithme (minimiser le nombre d’itérations).
On a :
abcabc = ax105 + bx104 + cx103 + ax102 + bx101 + cx100
= (103 + 1)(ax102 + bx101 + cx100)=1001(ax102 + bx101 + cx100)
Donc pour générer ces nombre il suffit de générer une partie (abc), ensuite la multiplier par 1001.
Algorithme Nombre ;
Var a,b,c,X,NBDiv :entier ; Pr :booleen ;
Fonction Premier(X : entier ): booleen;
--- --- ---
Fonction SemiPremier(X : entier ): booleen;
--- --- ---
Debut
/ trios boucles imbriquées Pour générer un nombre de la forme abcabc
Pour a ← 1 à 9
Faire Pour b ← 0 à 9
Faire Pour c ← 0 à 9
Faire
X ← 1001*(100*a+10*b+c) ;
Si SemiPremier(X) Alors Ecire(X,’ est semi premier’) Fsi ;
Fait ;
Fait ;
Fait ;
Fin.
Ajouter un commentaire
Veuillez vous connecter pour ajouter un commentaire.
Pas encore de commentaires.