À propos du crible d’Ératosthène - le plus ancien crible des nombres premiers
Le crible d’Ératosthène trouve tous les nombres premiers jusqu’à une limite sans une seule division. Il suffit de compter : barrez un nombre sur deux après 2, un sur trois après 3, et ainsi de suite. Ce qui reste, ce sont les nombres premiers. Plus de deux mille ans plus tard, c’est toujours l’une des méthodes les plus rapides pour les énumérer.
Ératosthène de Cyrène
Ératosthène a vécu d’environ 276 à 194 av. J.-C. et dirigeait la grande bibliothèque d’Alexandrie. Il est surtout connu pour avoir mesuré la taille de la Terre à partir de la longueur des ombres dans deux villes. Le crible porte son nom parce que Nicomaque de Gérase l’a décrit comme sa méthode dans l’Introduction arithmétique, écrite vers l’an 100.
Comment fonctionne le crible
Écrivez les nombres de 2 à N. Le premier nombre, 2, est premier : barrez 4, 6, 8 et tous les autres multiples de 2. Le nombre suivant qui reste, 3, est premier : barrez 9, 12, 15 et ainsi de suite. Continuez avec 5, 7 et les nombres suivants qui restent. Un nombre qui n’est jamais barré n’a pas de facteur plus petit, il est donc premier.
S’arrêter à la racine carrée
Chaque nombre composé jusqu’à N a un facteur premier qui ne dépasse pas la racine carrée de N. Dès que p² dépasse N, il n’y a donc plus rien à barrer. Pour trouver les premiers jusqu’à 100, il suffit de 2, 3, 5 et 7, et pour 1000 des premiers jusqu’à 31.
Quelle est sa rapidité ?
Le crible demande environ N log log N étapes, ce qui croît à peine plus vite que N lui-même. Les ordinateurs l’utilisent encore, souvent par morceaux sous la forme d’un crible segmenté, pour énumérer les nombres premiers jusqu’à des milliards. Pour tester si un seul grand nombre est premier, d’autres méthodes sont plus rapides.
Questions fréquemment posées
Qui a inventé le crible d’Ératosthène ?
Il porte le nom d’Ératosthène de Cyrène, un savant grec du IIIe siècle av. J.-C. La plus ancienne description écrite est celle de Nicomaque de Gérase, vers l’an 100.
Pourquoi le crible commence-t-il à barrer à p² ?
Chaque multiple plus petit de p a un facteur premier plus petit, donc un nombre premier plus petit l’a déjà barré.
Combien y a-t-il de nombres premiers inférieurs à 1000 ?
Il y a 168 nombres premiers inférieurs à 1000. Le plus grand est 997.
Outils associés
Crible d’Ératosthène
Regardez le crible d’Ératosthène trouver les nombres premiers jusqu’à 100, 200, 500 ou 1000. Chaque nombre premier barre ses multiples dans sa propre couleur, étape par étape.
Spirale d’Ulam
Tracez la spirale d’Ulam dans votre navigateur. Marquez les nombres premiers, lisez le polynôme du second degré de chaque diagonale et ouvrez la suite ininterrompue de 40 nombres premiers d’Euler.
La spirale d’Ulam
Comment la spirale de Stanisław Ulam, en 1963, dispose les entiers sur une grille carrée, pourquoi les nombres premiers se regroupent sur des diagonales quadratiques et où se trouvent les quarante nombres premiers d’Euler quand la spirale commence à 41.
La conjecture de Collatz
Explorez le problème de Collatz 3n+1 dans votre navigateur. Parcourez les suites de grêlons, faites pousser un arbre de Collatz géométrique et zoomez dans la fractale de Collatz continue.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer le crible d’Ératosthène