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 et N n’ont pas été rayés.
Pour évaluer l’efficacité du crible d’Ératosthène, on peut remarquer que si le produit de deux nombres p et q est égal à n, alors au moins un des deux nombres p ou q est inférieur (ou égal) à n\sqrt{n} : en effet, si les deux étaient plus grands que n\sqrt{n}, alors le produit pq serait lui-même plus grand que n×n=n,\sqrt{n} \times \sqrt{n} = n, alors que pq = n. On en déduit que, dans le crible d’Ératosthène, une fois rayés les multiples des entiers n pour tout n≤Nn \le \sqrt{N} il n’y a plus rien à rayer : le travail est fini.
Cette méthode globale de criblage n’est bien sûr pas vraiment applicable de tête, mais on peut s’en inspirer pour déterminer si un entier a donné est premier ou non. En effet, si a n’est pas premier, alors on peut l’écrire sous la forme pq et, d’après l’observation précédente, l’un de ces deux facteurs est au plus égal à a.\sqrt{a}. Il suffit donc de tester si a est divisible par 2, 3, etc. jusqu’à a,\sqrt{a}, ce qui est tout de même plus rapide que d’aller jusqu’à a − 1.