Prenez un entier positif x. Comment trouver tous les nombres premiers inférieurs ou égaux à x ? Il existe une méthode appelée le crible d’Eratosthène, dont l’histoire remonte à la Grèce antique. Les étapes du crible d’Eratosthène sont les suivantes :
- Premièrement, listez tous les entiers de 2 à x. Gardez 2 et supprimez tous les multiples de 2.
- Dans la liste restante, le premier nombre premier après 2 est 3. Gardez 3 et supprimez tous les multiples de 3.
- Dans la liste restante, le premier nombre premier après 3 est 5. Gardez 5 et supprimez tous les multiples de 5.
Et ainsi de suite. À la dernière étape, gardez le plus petit nombre premier inférieur ou égal à x dans la liste précédente, et supprimez tous ses multiples. La liste restante sera alors celle des nombres premiers inférieurs ou égaux à x.
Cette méthode repose sur le fait que si a n’est pas un nombre premier, il doit avoir un facteur inférieur ou égal à $.
Le crible d’Eratosthène peut être utilisé pour créer une table des nombres premiers assez facilement. Si vous rencontrez un entier positif non très grand (par exemple, inférieur à 10000) et que vous n’avez pas de table des nombres premiers sous la main, comment pouvez-vous déterminer rapidement s’il est un nombre premier ? En fait, il suffit de diviser a par tous les nombres premiers inférieurs ou égaux à $.