Comment pouvons-nous optimiser l'algorithme de tamisage d'Eratosthène en Python pour une génération plus rapide de nombres premiers ?

Tamis d'Eratosthène - Trouver des nombres premiers en Python

Problème :

Lors de la tentative d'implémentation l'algorithme Sieve of Eratosthenes en Python, les utilisateurs rencontrent souvent des temps d'exécution lents, en particulier lors de la recherche de nombres premiers supérieurs à 1 millions.

Solution :

La mise en œuvre donnée présente plusieurs domaines d'amélioration :

1. Algorithme non optimisé :

• L'implémentation initiale, primes_sieve, maintient une liste de nombres premiers, ce qui conduit à une suppression d'éléments inefficace.
• primes_sieve1 utilise un dictionnaire pour les indicateurs de primalité mais manque d'itération appropriée et marquage des facteurs redondants.

2. Inefficacité de la manipulation de liste :

• Supprimer un élément d'une liste Python est une opération coûteuse en raison de la nécessité de décaler les éléments suivants.

Mise en œuvre optimisée :

Pour résoudre ces problèmes, considérez les solutions optimisées suivantes implémentation :

def primes_sieve2(limit):
    a = [True] * limit
    a[0] = a[1] = False

    for (i, isprime) in enumerate(a):
        if isprime:
            yield i
            for n in range(i*i, limit, i):     # Mark factors non-prime
                a[n] = False

Améliorations clés :

• Utilise une liste directement pour les indicateurs de primalité, évitant ainsi un redimensionnement coûteux de la liste.
• Génère paresseusement nombres premiers à la demande, éliminant ainsi le besoin de stocker une liste complète.
• Marque efficacement les facteurs non premiers en commençant par le carré du premier.

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!