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

  1. Vérifie que n est un entier supérieur à 1.
  2. Repère les nombres premiers inférieurs ou égaux à √n.
  3. Teste la divisibilité de n par chacun d’eux.
  4. 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.

Et maintenant ?

Questions proches

← Toutes les questions-réponses