Nombres premiers et crible d'Ératosthène élémentaire de Collège

Terminale générale Spé · Option Mathématiques Expertes

À retenir

• Un entier p 2 est premier s'il a exactement deux diviseurs positifs : 1 et p ; 0 et 1 ne sont pas premiers. • 2 est le seul nombre premier pair. • Pour tester n, il suffit d'essayer les nombres premiers p tels que p^2 n. • Nombres premiers inférieurs à 30 : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

Le cours

1. Définition Un entier naturel p 2 est premier s'il possède exactement deux diviseurs positifs : 1 et lui-même. Un entier n 2 qui n'est pas premier est dit composé : il s'écrit n = a b avec 2 a b. Les nombres premiers inférieurs à 50 sont : 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47. Les nombres 0 et 1 ne sont pas premiers, et 2 est le seul nombre premier pair. 2. Tester si un nombre est premier Si n = a b avec 2 a b, alors a^2 a b = n. Un nombre composé a donc un diviseur premier p tel que p^2 n. 1. Lister les nombres premiers p tels que p^2 n. 2. Tester la divisibilité de n par chacun d'eux (critères de divisibilité ou division). 3. Si aucun ne divise n, alors n est premier. Exemple : pour 91, on teste 2, 3, 5, 7 et 91 = 7 13, donc 91 est composé. 3. Crible d'Ératosthène Pour obtenir tous les nombres premiers jusqu'à 50 : on écrit les entiers de 2 à 50 ; on garde 2 et on barre ses multiples ; le premier nombre non barré, 3, est premier : on barre ses multiples ; on fait de même avec 5 puis 7. On s'arrête là car 11^2 = 121 > 50 : les nombres non barrés sont premiers. 4. Attention Un nombre impair n'est pas forcément premier : 27, 39 et 49 sont impairs mais composés (49 = 7 7).

Dans ce chapitre