X Informatique PSI 2009

Thème de l'épreuve À propos des nombres premiers
Principaux outils utilisés arithmétique, programmation impérative

Corrigé

(c'est payant, sauf le début): - - - - - - - - - - - - -

Extrait gratuit du corrigé

(télécharger le PDF)
           

Énoncé complet

(télécharger le PDF)
           

Énoncé obtenu par reconnaissance optique des caractères


ÉCOLE POLYTECHNIQUE

CONCOURS D'ADMISSION 2009

FILIÈRES

PSI et PT

ÉPREUVE D'INFORMATIQUE
(Durée : 2 heures)
L'utilisation des calculatrices n'est pas autorisée pour cette épreuve.
Le langage de programmation choisi par le candidat doit être spécifié en tête 
de la copie.
On attachera une grande importance à la concision, à la clarté, et à la 
précision de la rédaction.
Chaque partie du problème utilise des notions introduites dans les parties 
précédentes.

À propos des nombres premiers
Le problème porte sur les entiers naturels, on utilisera les entiers fournis 
par le langage de
programmation choisi en supposant qu'ils sont les entiers naturels. Par 
ailleurs, étant donnés
deux entiers (naturels) a et b (b > 0) :
­ La notation a / b dans les programmes désigne le quotient de la division 
euclidienne de a
par b (parfois appelée « division entière »).
­ Une fonction mod(a, b) (avec a  0 et b > 0) donne le reste de la division 
euclidienne de a
par b.

­ Une fonction sqrt(a) donne la partie entière de la racine carrée de a (notée  
a).
Un entier b divise un entier a si a s'écrit comme le produit bq. Dans ce cas, 
on dit que b est un
diviseur (ou un facteur) de a. On observera que pour savoir si b divise a, il 
suffit de vérifier que
mod(a, b) vaut 0.
I. Nombres premiers
On rappelle qu'un entier supérieur ou égal à 2 est premier si et seulement si 
il n'est divisible que
par 1 et par lui-même.
Question 1. Écrire la fonction estPremier(n) qui prend un entier n (n  2) en 
argument, et
qui renvoie 1 si n est premier et 0 sinon. On appliquera directement la 
définition des nombres
premiers donnée ci-dessus.
On veut maintenant calculer tous les nombres premiers inférieurs à un entier 
donné n. On va
procéder selon trois méthodes différentes.

1

Question 2. Écrire la fonction petitsPremiers(n) qui prend en argument un 
entier n  2,
et qui :
1. Range (dans l'ordre croissant) les nombres premiers inférieurs ou égaux à n 
dans un tableau
global (ou prédéclaré) premier, que l'on supposera assez grand.
2. Renvoie le nombre d'entiers rangés dans premier.
Par exemple pour n = 17, votre fonction devra renvoyer 7 et remplir le début de 
premier ainsi :
2 3 5 7 11 13 17 · · ·
La fonction petitsPremiers sera la plus simple possible, des techniques plus 
efficaces sont l'objet
des deux questions suivantes.
Il est assez facile de voir que, pour tester si un entier impair m (3  m) est 
premier, il suffit de

vérifier que m n'est divisible par aucun nombre premier compris entre 3 et  m.

Question 3. Écrire une nouvelle fonction petitsPremiers2(n), qui agit comme 
petitsPremiers(n)
mais est plus efficace. Cette nouvelle fonction appliquera la remarque 
ci-dessus, les nombres

premiers entre 3 et  m étant lus dans le tableau premier en cours de 
remplissage.

Au IIIe siècle avant Jesus-Christ, Ératosthène, mathématicien, astronome et 
philosophe invente
une méthode efficace pour énumérer tous les nombres premiers inférieurs à un 
entier donné n.
Cette méthode est connue sous le nom de crible d'Ératosthène, que nous allons 
décrire en tenant
compte des moyens disponibles à l'époque.
1. Sur le sable, avec un bâton, dessiner un tableaux de (n-1) cases, la 
première case représente
2, la suivante 3 etc. Ramasser un caillou, le poser à gauche du tableau.
2. Avancer le caillou jusqu'à trouver une case non-rayée. Cette case représente 
l'entier i.
3. Ramasser un second caillou et le faire avancer par sauts de i cases. Pour 
chacune des cases
sur lesquelles le second caillou se pose :
(a) Si la case est déjà rayée, ne rien faire. (b) Sinon, rayer la case avec le 
bâton.
4. Poser le second caillou dès que l'on sort du tableau. Si l'étape (b) n'a pas 
été effectuée,
c'est fini. Sinon, recommencer en 2.
Les cases non-rayées représentent maintenant les
l'état du tableau au début de l'étape 4 et pour
étant « · » :
·
X
X
X
· X
X
X
X · X
X

nombres premiers. À titre d'exemple, voici
un tableau de 10 cases, le premier caillou

X
X

X
X
X

(i = 2)
(i = 3)
(i = 5)

Les nombres premiers trouvés sont donc 2, 3, 5, 7, 11.
Question 4. Écrire la fonction petitsPremiers3(n), qui agit comme 
petitsPremiers(n) mais utilise
le crible d'Ératosthène. On s'attachera à respecter l'esprit de cette 
technique, et en particulier à
éviter multiplications, divisions et racines carrées, difficiles à effectuer 
pour les mathématiciens
grecs.
On rappelle que tout entier n (n  2) peut s'écrire de manière unique comme le 
produit
n = p1 p2 · · · pk , où p1  p2  . . .  pk sont des nombres premiers. On appelle 
cette écriture la décomposition en facteurs premiers de n. Cette définition 
suggère un algorithme simple
2

pour décomposer n en facteurs premiers. Soit 1 , 2 , . . . la suite des nombres 
premiers en ordre
croissant.
1. Poser m = n, poser i = 1.
2. Si m = 1, alors terminer.
3. Si i divise m, alors i entre dans la décomposition de n. Poser m = m/i et 
aller en 3.
4. Sinon, poser i = i + 1 et aller en 2.
En résumé, l'algorithme, dit essai des divisions revient à diviser n par les 
nombres premiers.
Question 5. Écrire la fonction factoriser(n) qui prend en argument un entier n 
(n  2), et qui
range (dans l'ordre croissant au sens large) les facteurs premiers de n dans un 
tableau global
facteur, supposé assez grand. La fonction factoriser renvoie le nombre 
d'entiers rangés dans facteur.
Par exemple pour n = 90, votre fonction devra renvoyer 4 et remplir le début de 
facteur ainsi :
2 3 3 5 ···
Il n'est pas trop difficile de voir que, dans l'algorithme d'essai des 
divisions, on peut remplacer la
suite des nombres premiers par une suite plus simple à calculer, du moment que 
celle-ci commence
par 2, soit croissante, et contienne les nombres premiers -- par exemple, q1 = 
2, qj+1 = 2j + 1
(j  1). En effet, un invariant de l'algorithme est que, à l'étape 2, m n'est 
divisible par aucun des
entiers q1 , . . . , qi-1 , et donc par aucun nombre premier strictement 
inférieur à qi . Par conséquent,
si qi divise m (étape 3), alors qi est premier.
Par ailleurs, on peut limiter la taille des facteurs essayés. La suite des qi 
est strictement croissante,
tandis que m décroit. On finira donc par avoir qi2 > m. Dès lors, m, s'il n'est 
pas égal à 1, est premier, puisque non-divisible par q1 , q2 , . . . , qi-1 , 
séquence qui contient tous les nombres premiers

inférieurs ou égaux à  m. Dans ces conditions m est le dernier facteur de la 
décomposition
de n.
Question 6. Écrire une nouvelle fonction factoriser2(n) qui agit comme 
factoriser, mais ne
calcule pas de table de nombres premiers et exploite la seconde remarque 
ci-dessus.
II. Reconnaître les puissances
Une écriture courante de la décomposition en facteurs premiers regroupe les 
facteurs égaux :
n = p1 1 p2 2 · · · pk k ,

p1 < p2 < · · · < pk premiers,

0 < 1 , 0 < 2 , . . . , 0 < k

Les i sont les multiplicités de n -- en fait les multiplicités des facteurs 
premiers de n.
Question 7. Écrire la fonction calculerAlpha(n) (n  2) qui range les 
multiplicités dans un
tableau global alpha et renvoie le nombre d'entiers rangés dans alpha.
On admet que l'entier n (n  2) s'écrit comme la puissance n = ab , si et 
seulement si b divise
toutes les mutiplicités de n.
Question 8. Écrire la fonction estPuissance(n, b) (n  2, b  1) qui renvoie 1 si 
il existe un
entier a tel que n = ab et 0 sinon.
Question 9. La décomposition en facteurs premiers est une opération coûteuse. 
Proposer une
technique alternative pour détecter si un entier n est un carré ou pas. Aucun 
code n'est demandé.
3

III. Nombres de Carmichael
Par définition, un entier c est un nombre de Carmichael, si et seulement si :
­ L'entier c est impair et n'est pas premier.
­ La décomposition de c en facteurs premiers s'écrit c = p1 p2 . . . pk où p1 < 
p2 < . . . < pd .
­ Le nombre pi - 1 divise c - 1 pour tous les facteurs premiers pi de c.

On note que l'on a nécessairement 2  d et 3  p1 .

Question 10. Écrire la fonction estCarmichael(c) (c  2) qui renvoie 1 si c est 
un nombre
de Carmichael, et 0 sinon. On appliquera directement la définition des nombres 
de Carmichael
donnée ci-dessus.
Énumérer les nombres de Carmichael par la méthode évidente est trop coûteux. On 
s'intéresse
d'abord à une classe particulière de nombres de Carmichael : ceux de la forme c 
= p1 p2 p3 , dits
d'ordre 3.
Question 11. Écrire la fonction calculerCarmichael3(n) (n  2) qui range les 
nombres de
Carmichael d'ordre 3 inférieurs ou égaux à n dans un tableau global carmichael. 
La fonction
calculerCarmichael3(n) renvoie le nombre d'entiers rangés dans le tableau. On 
utilisera la méthode
suivante :
­ Calculer les nombres premiers entre 3 et n.
­ Tester la dernière condition de la définition des nombres de Carmichael pour 
tous les
produits possibles de trois de ces nombres.
Pour trouver tous les nombres de Carmichael inférieurs à n, il existe une 
technique de criblage
assez efficace. On commence par se donner un tableau d'entiers t de n + 1 
cases, de sorte que la
case d'indice i représente l'entier i. Initialement, la case d'indice i 
contient i. Puis . . .

­ Pour chaque nombre premier p, compris entre 3 (inclus) et  n (exclu).
­ Pour chaque indice i valide, de la forme i = p2 + k · p(p - 1) (k entier 
naturel).
­ Poser t[i] = t[i]/p.

Maintenant, les indices plus grands que 2 qui désignent une case dont le 
contenu vaut 1 sont
exactement les nombres de Carmichael recherchés.
Question 12. Écrire la fonction calculerCarmichael(n) (n  2) qui range les 
nombres de Carmichael inférieurs ou égaux à n dans le tableau global 
carmichael. La fonction calculerCarmichael(n)
renvoie le nombre d'entiers rangé dans le tableau. On utilisera la technique de 
criblage décrite
ci-dessus.

4

Extrait du corrigé obtenu par reconnaissance optique des caractères



X Informatique PSI 2009 -- Corrigé
Ce corrigé est proposé par Vincent Puyhaubert (Professeur en CPGE) ; il a été
relu par Arnaud Borde (École Polytechnique) et Céline Chevalier (ENS Cachan).

Le sujet d'informatique de cette année a pour thème l'arithmétique. Il a pour
objectif de donner des méthodes pour calculer la suite des nombres premiers, la 
décomposition d'un entier en facteurs premiers, et des nombres dits de 
Carmichael.
· La première partie demande de programmer différentes méthodes pour trouver
tous les nombres premiers plus petits qu'un entier n ; les techniques sont très
classiques, de la méthode la plus élémentaire à une méthode optimisée (crible
d'Érathostène). On programme ensuite la factorisation d'un entier.
· La deuxième partie fait programmer une méthode pour répondre à la question :
un entier n donné est-il puissance d'un autre entier ?
· Enfin, la dernière partie introduit les nombres de Carmichael et propose 
diverses
méthodes pour les calculer.
Dans l'ensemble, les programmes à écrire ne sont pas très compliqués. C'est même
un aspect décevant du sujet : les algorithmes donnés par l'énoncé sont tellement
détaillés qu'il ne reste plus vraiment de place pour la réflexion. Mais si vous 
n'avez
pas l'habitude de programmer, c'est un très bon entraînement.
L'énoncé ne précise pas le contexte historique des nombres de Carmichael, 
notamment leur rôle dans le petit théorème de Fermat. Cette lacune sera comblée 
en
annexe à ce corrigé.

Indications
1 Tester sans subtilités la divisibilité de n par tous les entiers compris 
entre 2 et n-1.
2 Ne tester cette fois la divisibilité que par les éléments de premier. 
Utiliser un
compteur pour mettre à jour le nombre d'éléments de ce tableau.
3 Remplir le tableau premier au fur et à mesure, et ne tester les divisibilités 
que
par des éléments de ce tableau.
4 Utiliser un tableau initialisé avec des 1. Rayer une case revient alors à 
passer sa
valeur à 0.
7 Il faut parcourir le tableau facteur à l'aide de deux boucles while et deux 
compteurs. Le premier sert à compter le nombre de facteurs distincts de n, le 
second
le nombre d'occurrences de ces facteurs.
8 Utiliser le résultat admis de l'énoncé et les multiplicités stockées dans le 
tableau
alpha.
9 Calculer les carrés des entiers naturels jusqu'à tomber sur n ou le dépasser.
10 Il faut simplement effectuer tous les tests intervenant dans la définition 
des
nombres de Carmichael. Pour avoir accès aux facteurs premiers de n, utiliser
facteur et alpha.
11 Utiliser trois boucles for pour calculer tous les produits de 3 nombres 
premiers
inférieurs ou égaux à n. Tester ensuite s'il s'agit de nombres de Carmichael.

I. Nombres premiers
Les fonctions de ce corrigé sont toutes rédigées dans le langage Maple.
Toutefois, le quotient et le reste de la division euclidienne de deux entiers a 
et b s'obtiennent dans ce langage respectivement par les commandes
iquo(a,b) et irem(a,b). Ces commandes ne sont pas utilisées dans les programmes 
car l'énoncé impose les notations a/b et mod(a,b). Pour obtenir
des codes qui fonctionnent, il faut donc remplacer ces notations par les vraies
fonctions.
De la même manière, une racine carrée s'obtient elle aussi par la commande 
sqrt, mais elle renvoie un nombre réel avec une certaine précision.
Pour obtenir un entier, on doit en réalité la combiner avec la fonction partie
entière, c'est-à-dire la commande floor.
1 Si n est divisible par un entier autre que 1 et lui-même, ce dernier est 
compris
entre 2 et n - 1. Par suite, il suffit de tester la divisibilité de n par tous 
les éléments
de [[ 2 ; n - 1 ]] (l'énoncé ne demande pas d'optimisation). Dès qu'un diviseur 
de n est
trouvé, il ne sert plus à rien de tester les entiers suivants, donc on renvoie 
0 immédiatement (rappelons au passage qu'en Maple, un return termine 
automatiquement
l'exécution du programme). Si tous les tests ont échoué, l'entier est premier 
et on
renvoie 1.
estPremier:=proc(n)
local i;
for i from 2 to (n-1) do
if mod(n,i)=0 then
# n est divisible par i:
return 0;
# il n'est pas premier
fi;
od;
return 1;
end;
2 La première méthode naïve consiste à prendre successivement tous les entiers
compris entre 2 et n et à tester (à l'aide de estPremier) s'ils sont premiers ; 
on range
ceux qui le sont dans le tableau premier. La seule difficulté est de penser à 
utiliser
une variable pour savoir combien de nombres premiers ont déjà été stockés dans 
ce
tableau, ce qui se fait à l'aide d'un compteur k.
petitsPremiers:=proc(n)
local i,k;
global premier;
k:=0;
for i from 2 to n do
if estPremier(i)=1 then
k:=k+1; premier[k]:=i;
fi;
od;
return k;
end;

Dans ce programme et dans tous ceux qui suivent, il ne faut pas oublier de
créer les variables globales avant de tester les fonctions dans Maple (ce n'est
pas indispensable sur une copie). Le tableau premier peut par exemple être
initialisé par
premier:=[seq(0,i=1..30)];
et il peut alors contenir 30 nombres premiers (sachant que le trentième
nombre premier est 113).
3 La fonction utilise l'amélioration donnée par l'énoncé. Il s'agit toujours de 
tester
la primalité des entiers de 1 à n, à l'aide d'une boucle for. Toutefois, plutôt 
que de
faire appel à la fonction estPremier, peu efficace, on teste uniquement la 
divisibilité
par les éléments stockés dans le tableau premier (c'est le rôle de la boucle 
while).
L'arrêt des tests de divisibilité se fait soit lorsque la liste des nombres 
premiers est
épuisée, soit lorsque le facteur est supérieur à la partie entière de la racine 
carrée
de n.
petitsPremiers2:=proc(n)
local i,j,k,test,max;
global premier;
premier[1]:=2;
# 2 est le premier nombre a stocker
k:=1;
# le tableau premier contient 1 nombre premier
max:=sqrt(n);
for i from 3 by 2 to n do
test:=1;
# test vaut 1 tant que n est supposé premier
j:=1;
while j