Les nombres premiers - Maxicours

Les nombres premiers

Objectifs
  • Connaitre la définition d’un nombre premier.
  • Résoudre des problèmes mobilisant cette notion.
  • Déterminer à l’aide d’un algorithme si un entier naturel non nul est premier.
Points clés
  • On appelle nombre premier tout entier naturel qui n'admet que deux diviseurs distincts positifs : lui-même et 1.
  • La liste des entiers premiers positifs débute par :
    2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31…
  • Soit un entier naturel. Si aucun entier premier inférieur ou égal à autre que 1 ne divise , alors est un entier premier.
Pour bien comprendre
  • Nombres entiers naturels et relatifs
  • Multiples et diviseurs
  • Algorithmique
1. Définition
On appelle nombre premier tout entier naturel qui n'admet que deux diviseurs distincts positifs : lui-même et 1.
Remarque
Les nombres 0 et 1 ne sont pas des nombres premiers.
En effet, 0 a une infinité de diviseurs et 1 n’a que lui-même pour diviseur positif.
Exemples
2, 3, 5, 11, 31 sont des nombres premiers.
21 admet quatre diviseurs positifs (1, 3, 7 et 21) donc ce n'est pas un nombre premier.
Propriété
La liste des nombres premiers débute par :
2 ; 3 ; 5 ; 7 ; 11 ; 13 ; 17 ; 19 ; 23 ; 29 ; 31…
2. Test de primalité

Un test qui détermine si un nombre entier est premier est appelé « test de primalité ».

Propriété
Soit un entier naturel. Si aucun entier premier inférieur ou égal à autre que 1 ne divise , alors  est un entier premier.
Méthode

Pour tester si un entier est premier :

  1. calculer sa racine carrée  ;
  2. tester si  est divisible par tous les entiers naturels  premiers compris entre 2 et .
    Si un de ces entiers divise , alors c’est un diviseur de autre que 1 et , donc  n’est pas premier. Sinon, est premier ;
  3. conclure.
Exemple 1
est-il premier ?
On calcule .
La liste des entiers premiers positifs inférieurs à 11 est {2 ; 3 ; 5 ; 7 ; 11}. On teste la divisibilité de 139 par ces nombres.
  • 139 n’est pas divisible par 2 ni par 5.
  • 3 × 46 = 138 donc 139 n’est pas divisible par 3.
  • 7 × 20 = 140 donc 139 n’est pas divisible par 7.
  • Enfin, 11 × 12 = 132 et 11 × 13 = 143 donc 139 n’est pas divisible par 11.

Par conséquent, 139 est premier.

Exemple 2
est-il premier ?
On calcule .
La liste des entiers premiers positifs inférieurs à 8 est {2 ; 3 ; 5 ; 7}. On teste la divisibilité de 69 par ces nombres.
  • 69 n’est pas divisible par 2.
  • Mais 3 × 23 = 69, donc 69 est divisible par 3.
Par conséquent, 69 n’est pas premier.
3. Programmation

On peut déterminer à l’aide d’un programme si un entier naturel non nul est premier ou non.

Pour cela, on teste s’il est divisible par un des entiers inférieurs ou égaux à 29. Ainsi, on peut appliquer l’algorithme à tout entier inférieur ou égal à 29= 841.

Ce programme affiche 1 si l’entier n est premier et 0 sinon.

Langage naturel   Langage Python
L=[2,3,5,7,11,13,17,19,23,29]
Saisir n
test ←1
k ← 0
Tant que test=1 et que k<=9
  K ← l’entier L[k]
  Si K divise n alors
    test ← 0
    kk+1
  Fin Si
Fin Tant que
Afficher test
L1 L=[2,3,5,7,11,13,17,19,23,29]
L2 n=input('n ?')
L3 n=int(n)
L4 test=1
L5 k=0
L6 while test==1 and k<=9:
L7   K=int(L[k])
L8   if n%K==0:
L9      test=0
L10  k=k+1
L11 print(test)

Quelques précision sur les instructions

  • L1 : on définit la liste qui contient les nombres premiers inférieurs ou égaux à 29.
  • L3 : l’instruction int permet de transformer le type d’une variable en entier. En effet, pour déterminer le reste d’une division entre deux entiers, il faut deux variables numériques de type entier.
  • L6 : la condition de la boucle while est vraie tant qu’on n’a pas trouvé de diviseur à n (test==1) et qu’on n’a pas passé en revue les entiers de la liste L (K<=9) pour savoir s’ils divisent n.
  • L8 : l’instruction n%K donne le reste de la division euclidienne de n par K. Si ce reste est égal à 0, alors n est divisible par K et n’est pas un entier.

Vous avez déjà mis une note à ce cours.

Découvrez les autres cours offerts par Maxicours !

Découvrez Maxicours

Comment as-tu trouvé ce cours ?

Évalue ce cours !

 

quote blanc icon

Découvrez Maxicours

Exerce toi en t’abonnant

Des profs en ligne

  • 6j/7 de 17 h à 20 h
  • Par chat, audio, vidéo
  • Sur les matières principales

Des ressources riches

  • Fiches, vidéos de cours
  • Exercices & corrigés
  • Modules de révisions Bac et Brevet

Des outils ludiques

  • Coach virtuel
  • Quiz interactifs
  • Planning de révision

Des tableaux de bord

  • Suivi de la progression
  • Score d’assiduité
  • Un compte Parent