Comment tester si un entier est premier en s’arrêtant à sa racine carrée ?
Réponse courte
Pour tester si n>1 est premier, essaie ses diviseurs premiers jusqu’à √n. Si aucun ne divise n, il est premier ; tout facteur plus grand aurait un partenaire plus petit que √n.
Comprendre
Pourquoi la recherche s’arrête
Si n est composé, il existe deux entiers a et b supérieurs à 1 tels que n=ab. Ils ne peuvent pas être tous les deux strictement supérieurs à √n, car leur produit dépasserait n. Ainsi, au moins un diviseur de n est inférieur ou égal à √n. Il suffit donc de chercher jusque-là.
Faire le test
Pour n=97, √97 est compris entre 9 et 10. On teste les nombres premiers 2, 3, 5 et 7 : 97 n’est divisible par aucun, donc 97 est premier. Pour n=91, √91 est entre 9 et 10, et 91=7×13 ; le test découvre le diviseur 7 et conclut que 91 est composé.
Organiser les essais
Tester seulement les nombres premiers suffit : si un entier composé divise n, l’un de ses facteurs premiers divise aussi n. Pour un petit nombre, les essais peuvent être faits à la main ; pour un nombre plus grand, on détermine d’abord une borne entière dont le carré encadre n.
Deux pièges
N’oublie pas le cas n≤1 : ni 0, ni 1 n’est premier. Et si √n n’est pas entier, un diviseur entier égal à la partie entière de √n reste à tester lorsqu’il est premier.
Étapes
- Vérifie que n est un entier supérieur à 1.
- Repère les nombres premiers inférieurs ou égaux à √n.
- Teste la divisibilité de n par chacun d’eux.
- Conclue premier seulement si tous les restes sont non nuls.
Exemples
- 97 : √97<10 ; 97 n’est divisible ni par 2, 3, 5 ni 7, donc 97 est premier.
- 91 : 91=7×13, avec 7≤√91, donc 91 n’est pas premier.
Pièges fréquents
- S’arrêter à √n sans inclure cette borne : si n=49, le diviseur 7 vaut exactement √49.
- Déclarer 1 premier : la définition exige un entier strictement supérieur à 1 ayant exactement deux diviseurs positifs.
Pourquoi ça marche
Tout facteur supérieur à √n s’accompagne d’un facteur inférieur à √n ; un composé ne peut donc échapper à tous les essais jusqu’à cette borne.
