FORMATION D'UNE TABLE DE NOMBRES PREMIERS

IH. La méthode la plus simple pour former la Table des nombres premiers compris entre i et une limite L est connue sous le nom de crible d'Ératost/iène. Yoici en quoi elle consiste. On écrit la suite

I, 2, 3, 4. 5, 6, 7, 8, 9, 10, II, 12, i3, i4, l'î, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 3o, 3i, 32, 33, 34, 35,

que l'on continue jusqu'à la limite L, et l'on barre dans cette suite tous les nombres qui ne sont pas premiers.

Les deux premiers nombres i et 2 satisfont à la définition des nombres premiers et doivent être conservés.

En barrant les nombres de la suite de deux en deux, à partir de 2 exclusivement, on supprime tous les multiples de 2 excepté 2. Le premier nombre conservé après 2 est 3, qui est un nombre premier.

On barre alors les nombres de la suite de trois en trois, à partir de 3 exclusivement, et l'on supprime ainsi tous les nombres divisibles par 3, excepté 3. Le premier nombre conservé après 3 étant 5, 5 est un nombre premier, puisqu'il n'est divisible par aucun des nombres premiers plus petits que lui, sauf l'unité.

s. et do C. — Arithm. ^

On continue de la même manière, en barrant les nombres de la suite de 5 en 5, à partir de 5 exclusivement, de façon à supprimer tous les multiples de 5, excepté 5; puis de 7 en 7, à partir do 7 exclusivement, etc.

Supposons qu'en poursuivant ces opérations, dont la marche est régulière et uniforme, on ail barré les termes de la suite de deux en deux, de trois en trois, . . ., de p en /? ; la suite 2, 3,. . ., p sera celle des nombres premiers jusqu'à p. Si fj estalors le premier nombre non barré après/?, q est le nombre premier immédiatement supérieur à p. 11 est facile de voir que tous les nombres non barrés, inférieurs au carré ç% sont des nombres premiers.

Soit, en effet, un nombre non barré N plus petit que q\ Si ce nombre n'était pas premier, il admettrait un diviseur premier N' ( 113} supérieur à p, c'est-à-dire égal à ^ ou plus grand que q. Le quotient de N (qui est moindre que ç')par N' serait alors inférieur à ^, et N aurait un diviseur inférieur à q, qui serait premier ou admettrait lui-même un diviseur premier. Dans tous les cas, N aurait un diviseur premier inférieur à q, c'est-à-dire au plus égal à /? : il aurait donc été barré comme multiple de ce diviseur premier.

Par conséquent, si q^ surpasse la limite L, tous les nombres non premiers de i à L se trouvent barrés, et ceux qui restent sont les nombres premiers demandés. Si, au contraire, q^ est inférieur à L, il faut continuer les opérations, en commençant par barrer les multiples de q, à partir de q^ inclusivement.

115. Un nombre est premier lorsqu'il n'est divisible par aucun des nombres premiers dont les carrés sont moindres que lui.

En effet, il résulte du raisonnement précédent (114) que, dans ce cas, le nombre proposé ne peut non plus être divisible par aucun des nombres premiers dont les carrés le surpassent.

Par conséquent, un nombre N étant donné, pour reconnaître s'il est premier ou non, on n'a qu'à le diviser successivement par tous les nombres premiers dont les carrés sont plus petits que lui. Si aucune division ne se fait exactement, on en conclut que N est premier.

On est d'ailleurs averti que le carré />' d'un nombre pre-

mierp surpasse N, lorsque le quotient de N par /> est inférieur à p.

116. On a construit depuis longtemps, par le procédé indiqué (114), des Tables de nombres premiers. Celles de Burckhardt, qui sont le plus répandues, contiennent les nombres premiers de i à 3o36ooo et les plus petits diviseurs des autres nombres. On voit, par l'inspection de ces Tables, qu'il y a 26 nombres premiers de i à 100; qu'il y en a 169 de i à 1000 ; 1280 de I à loooo; 9392 de i à looooo; 78493 de i à loooooo.

Nous plaçons ici une Table des nombres premiers jusqu'à i5oo.

Table des nombres premiers inférieurs à i5oo.

ii63

lOI

ioi3

io3

io3i

ii3

io33

io5i

io63

9ii

iio3

ii83

6'fi

i3oi

ii5i