Le "Tamis d'Eratosthenos" vous permet de trouver n'importe quel nombre premier inférieur à un nombre spécifié. La méthode vieille de 2 000 ans fait maintenant l'objet d'une mise à jour.
Les nombres premiers ne sont divisibles que par 1 et eux-mêmes. Ils occupent une place très particulière en arithmétique, car tout nombre naturel peut être formé en multipliant des nombres premiers entre eux.
Les anciens Grecs le savaient déjà, ou du moins les philosophes grecs qui étaient impliqués dans le noble art des mathématiques. En 240 avant JC, le philosophe naturel ptolémaïque Eratosthène a conçu une méthode pour détecter les nombres premiers. Son soi-disant "tamis" fonctionne comme suit. Par exemple, prenez les nombres de 1 à 100. D'abord vous « tamisez » tous les multiples de 2, le premier nombre premier. Donc, vous enlevez 2, 4, 6, 8 et ainsi de suite. Ensuite, vous recommencez avec le plus petit nombre restant :puis vous supprimez tous les multiples de 3. Ensuite, vous devez d'abord passer au crible les multiples de 5, puis les multiples de 7, et ainsi de suite jusqu'à ce que vous ne puissiez plus aller plus loin. Tout nombre avec lequel vous démarrez le processus - et qui n'a pas encore été supprimé - est un nombre premier.
La méthode fonctionne bien pour détecter des nombres premiers relativement petits. Mais pour de très grands nombres, il est inutilisable, en raison du temps et de la mémoire énormes que nécessitent les ordinateurs. C'est pourquoi les mathématiciens ont amélioré le tamis dans les années 1960. Ils ont réalisé que pour tous les nombres premiers inférieurs à un nombre spécifié N, un ordinateur n'avait besoin que d'un nombre d'unités de mémoire égal à la racine carrée de ce nombre N.
Cependant, cette nouvelle méthode s'est également avérée peu pratique pour les très grandes valeurs de N. C'est pourquoi un mathématicien allemand a de nouveau proposé une mise à niveau. Il utilise pour cela l'approche rationnelle des nombres réels - en écrivant les nombres décimaux sous forme de fraction, comme 355/113 pour le nombre pi.
Dans la mise à niveau, le nombre d'unités de mémoire nécessaires pour trouver tous les nombres premiers inférieurs à N est désormais uniquement égal à la racine cubique de N fois une racine de son logarithme. Avec cette version du 21ème siècle du crible d'Eratosthène, un milliard de nombres peuvent être "criblés" avec seulement 7 500 unités de mémoire.
