Le crible d'Ératosthène permet d'identifier tous les nombres premiers inférieurs à un nombre donné. Cette méthode ancestrale, vieille de plus de 2 000 ans, bénéficie aujourd'hui d'une mise à niveau révolutionnaire.
Les nombres premiers, divisibles uniquement par 1 et par eux-mêmes, sont les fondements de l'arithmétique : tout nombre naturel résulte de leur multiplication.
Vers 240 av. J.-C., Eratosthène de Cyrène, érudit ptolémaïque et directeur de la bibliothèque d'Alexandrie, inventa ce "tamis". Principe : listez les entiers de 2 à N. Éliminez les multiples de 2, puis de 3, de 5, de 7... jusqu'à la racine carrée de N. Les survivants sont premiers.
Efficace pour les petits N, il devient impraticable pour les très grands en raison des besoins en temps et mémoire. Dans les années 1960, les mathématiciens l'ont optimisé : un ordinateur ne stocke plus que jusqu'à la racine carrée de N.
Cette version reste limitée pour les N colossaux. Un mathématicien allemand propose une nouvelle amélioration via des approximations rationnelles des réels (comme 355/113 pour π).
Désormais, la mémoire requise équivaut à la racine cubique de N multipliée par la racine de son logarithme. Ainsi, un milliard de nombres se criblent avec seulement 7 500 unités de mémoire.
