Quelle est la méthode la plus simple pour savoir si un nombre est premier ? L’adage qui stipule que mille chemins mènent à Rome se vérifie davantage en math. En effet, dans cette discipline, plusieurs méthodes permettent d’aboutir à la même solution pour un problème.
D’autres méthodes peuvent paraître plus simples que d’autres, cela est une question de relativité. Découvrez ici les différentes méthodes pour déterminer les nombres premiers afin d’opter pour la plus simple pour vous.
A lire également : Les faits qui se sont passés en vrai et qui se trouvent dans le film conjuring
Plan de l'article
Méthode la plus simple pour savoir si un nombre est premier : le crible d’Eratosthène
Pour rappel, un nombre premier désigne tout entier naturel qui n’admet pas plus de deux différents diviseurs entiers et positifs. Il s’agit en effet du nombre lui-même et de 1. Dans cette proposition des méthodes les plus simples pour savoir si un nombre est premier, le crible d’Eratosthène occupe la première place.
En quoi consiste cette méthode ?
Le scribe d’Eratosthène repose sur la méthode des essais de division. Il consiste à prendre une valeur donnée et à fournir la liste des nombres premiers inférieurs à cette dernière en supprimant les non concernés.
A lire en complément : Mythe des roux sans âme : origine et vérité derrière la croyance
Application du crible d’Eratosthène
En prenant par exemple le nombre 120, vous allez dresser la liste de tous les nombres qui lui sont inférieurs en commençant par 2. En effet, 0 et 1 sont d’office rayés de la liste si vous vous conformez à la définition de nombre premier ci-dessus mentionnée. Alors, vous aurez une liste partant de 2 jusqu’à 120.
Le premier nombre sur la liste (2) est le premier nombre premier. Vous l’encerclez, puis vous barrez tous ses multiples. Ensuite, vous encerclez le deuxième chiffre qui le suit immédiatement et qui n’est pas barré. C’est le deuxième nombre premier de votre liste. Vous barrez également tous ses multiples.
Vous répétez cette opération pour vous arrêter sur le premier entier supérieur à la racine carrée de la valeur. Dans ce cas d’espèce, il s’agit de 120, dont la racine carrée équivaut à 10,9 environ. 11 est donc le premier nombre premier supérieur à ce dernier. Vous vous arrêtez donc sur ça et vous recopiez tout le reste des entiers qui n’ont pas été barrés à partir de 2 bien sûr.
La méthode de l’algorithme par essais de division
L’algorithme par essais de division fait partie le scribe d’Eratosthène est l’une des premières méthodes de calcul des nombres premiers. Celles-ci se font appeler tests de primalité.
Leur principe consiste à essayer de diviser la valeur choisie par tous les nombres inférieurs à sa racine carrée. Ainsi, si la valeur est divisible par l’un des nombres qui lui sont inférieurs, ce dernier est composé. Dans le cas contraire, il s’agit d’un nombre premier.
Par ailleurs, l’essai par division est un algorithme assez long qui peut être fastidieux. En effet, il vous emmène à réaliser beaucoup de divisions inutiles. Par exemple, si un nombre n’est pas divisible par 2, vous devez reprendre avec 3, puis 4, etc.
La méthode du crible de Sundaram
Le crible de Sundaram est une variante du crible d’Eratosthène. C’est une méthode qui vous permet aussi d’identifier un nombre premier. La procédure dans ce cas va consister à établir une liste des entiers naturels impairs composés à l’aide de suites arithmétiques placées en colonne. Ce qui vous donne par la suite la possibilité de déduire facilement les nombres premiers.
À part les scribes d’Eratosthène et de Sundaram, il existe également plusieurs autres méthodes qui permettent de déterminer les nombres premiers. Vous avez entre autres :
- l’algorithme AKS ;
- le test de primalité de Miller-Rabin ;
- le test de primalité de Solovay-Strassen ;
- les premiers de Woodall ;
- les premiers de Proth ;
- le crible général des corps de nombres, etc.
Toutefois, parmi toutes ces méthodes, celles basées sur l’essai de division peuvent paraître longues, mais ce sont les plus faciles à adopter.
Les nombres premiers particuliers
En dehors des nombres premiers simples que vous pouvez identifier à l’aide d’une des méthodes mentionnées ci-dessus, il existe d’autres types de nombres premiers. Il s’agit des nombres premiers particuliers. Ces derniers sont définis par des contraintes spéciales. Ils sont :
- les nombres premiers de Pythagore ;
- les nombres premiers de Mersenne ;
- les nombres premiers de Fermat ;
- les nombres premiers jumeaux ;
- les nombres premiers de Sophie Germain ;
- les nombres premiers brésiliens.
Leur maîtrise nécessite une étude approfondie.