X Informatique PSI 2009

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

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