🔢 Crible d'Ératosthène — Chercheur animé de nombres premiers

Tout multiple composé de p inférieur à p² — comme 2p, 3p, …, (p−1)p — possède déjà un facteur premier plus petit que p, donc il a été rayé lors d'un passage précédent lorsque ce nombre premier plus petit a été traité. Commencer chaque passage à p² évite un travail redondant et est l'optimisation clé qui donne au crible son temps d'exécution en O(N log log N) au lieu d'un O(N log N) plus lent.

La vue en spirale d'Ulam prend exactement le même tableau de crible utilisé dans la vue en grille et retrace chaque nombre premier survivant le long d'un chemin en spirale carrée qui s'enroule vers l'extérieur depuis le centre, une cellule par entier. Visuellement, les nombres premiers ont tendance à s'agglutiner le long de certaines lignes diagonales dans cette disposition — un motif frappant, encore non entièrement expliqué, remarqué pour la première fois par le mathématicien Stanisław Ulam en 1963 alors qu'il griffonnait lors d'une conférence ennuyeuse.

π(x) est la fonction de comptage des nombres premiers : le nombre réel de nombres premiers inférieurs ou égaux à x, compté directement à partir du crible pendant son exécution. x/ln(x) est l'approximation asymptotique de premier ordre issue du théorème des nombres premiers (démontré indépendamment par Hadamard et de la Vallée Poussin en 1896). Les deux courbes se rapprochent de plus en plus l'une de l'autre à mesure que N croît, ce qui est exactement ce que prédit le théorème — bien que le rapport ne converge vers 1 qu'à la limite x → ∞.

Le travail total est proportionnel à N multiplié par la somme de 1/p sur tous les nombres premiers p ≤ √N (un « coup » par multiple de chaque nombre premier). Selon le second théorème de Mertens, la somme des inverses des nombres premiers jusqu'à une borne croît comme le logarithme du logarithme de cette borne, donc le travail total évolue comme N·log log N — asymptotiquement proche du linéaire et bien plus rapide que de diviser individuellement chaque nombre par essai.

Elle rapporte la plus grande différence entre nombres premiers consécutifs trouvés jusqu'à la limite N actuelle (par exemple, l'écart de 8 entre 89 et 97). Les écarts entre nombres premiers croissent irrégulièrement mais s'élargissent en moyenne comme ln(N) à mesure que N augmente, selon le théorème des nombres premiers ; la conjecture de Cramér propose une borne plus stricte sur la taille que peut atteindre un écart individuel, mais elle reste non démontrée.

Non — le crible peut énumérer chaque paire de nombres premiers jumeaux (p, p+2) en dessous de la limite N choisie, mais cela ne confirme que finiment d'exemples. La conjecture des nombres premiers jumeaux affirme qu'il existe une infinité de telles paires, ce qui est un énoncé portant sur tous les nombres premiers, pas un calcul fini ; malgré de solides preuves numériques et théoriques partielles (y compris la percée de Zhang en 2013 sur les écarts bornés), elle reste un problème ouvert en théorie des nombres.