Comment pouvons-nous optimiser le tamis d'Eratosthène pour une génération efficace de nombres premiers en Python ?

Le tamis d'Eratosthène : optimisation de la génération de nombres premiers en Python

Le tamis d'Eratosthène est un algorithme classique pour trouver des nombres premiers. Cependant, il est crucial de l'implémenter correctement pour éviter les goulots d'étranglement des performances.

Implémentation originale

La fonction primes_sieve fournie maintient une liste de nombres premiers candidats et supprime de manière itérative les nombres non- prime en parcourant la liste et en éliminant les facteurs. Cette approche est intrinsèquement inefficace en raison du coût élevé de la manipulation de liste.

Optimisation basée sur un dictionnaire

La fonction améliorée primes_sieve1 utilise un dictionnaire pour stocker les indicateurs de primalité. Bien que plus rapide que l’approche basée sur des listes, elle reste néanmoins confrontée à des défis. Il parcourt le dictionnaire dans un ordre indéfini, provoquant un marquage redondant des facteurs non premiers. De plus, il convertit le dictionnaire final en liste, ce qui entraîne une surcharge inutile.

Mise en œuvre correcte et efficace

L'algorithme correct du tamis d'Eratosthène utilise une liste d'indicateurs booléens pour indiquer la primalité. La fonction primes_sieve2 initialise les indicateurs à True pour tous les nombres et définit les indicateurs de 0 et 1 sur False. Il parcourt la liste, marquant les non premiers en définissant leurs indicateurs sur False.

Cette approche est efficace car :

• Elle utilise une liste au lieu d'un dictionnaire, évitant ainsi la surcharge d'opérations clé-valeur.
• Il marque uniquement les facteurs premiers comme non premiers, réduisant ainsi les opérations redondantes.
• Il optimise le processus de marquage en commençant par le carré de chaque nombre premier au lieu de son double.

En implémentant correctement le tamis d'Eratosthène, vous pouvez améliorer considérablement les performances de génération de nombres premiers, le rendant adapté même aux grandes limites d'entrée comme trouver des nombres premiers inférieurs à 2 millions.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!