Un nombre premier est un nombre plus grand que 1 et qu’on ne peut diviser que par lui-même et par 1. Une telle définition suggère, pour savoir si le nombre n est premier ou non, d’effectuer consciencieusement la division euclidienne de n par 2, puis par 3, et ainsi de suite jusqu’à ce que l’une d’elles tombe juste ou que l’on ait testé n − 1. Pas vraiment rapide, et encore moins évident à faire mentalement… Heureusement, un peu d’arithmétique permet de grandement réduire les opérations à effectuer, au point de rendre la détermination de la primalité de n un exercice que l’on peut faire de tête pour beaucoup de nombres pas trop grands.
Le crible paie
On prête à Ératosthène, directeur de la bibliothèque d’Alexandrie et correspondant d’Archimède, la paternité d’un procédé pour trouver tous les nombres premiers inférieurs à une valeur N préalablement fixée : on écrit la liste des nombres entiers entre 2 et N, on garde 2 et on raye tous ses multiples, puis on garde 3 et on raye tous ses multiples, puis on garde 5 (4 ayant été rayé) et on raye tous ses multiples, et ainsi de suite. À la fin, seuls les nombres premiers entre 2 ... Lire la suite