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

Tamis d'Eratosthène amélioré : optimisation de la génération de premiers Python

Le Tamis d'Eratosthène est un algorithme efficace pour trouver des nombres premiers jusqu'à une limite prédéfinie . Cependant, une implémentation naïve de Python peut être excessivement lente pour des limites plus grandes.

Identification des goulots d'étranglement

Dans l'exemple fourni, le profilage a révélé qu'un temps important était nécessaire pour supprimer des éléments de la liste (primes). Cette opération est coûteuse en calcul, en particulier pour les longues listes.

Substitution des listes par des dictionnaires

Une première tentative pour résoudre ce problème impliquait de remplacer la liste par un dictionnaire (nombres premiers). . Cela a permis un retrait plus rapide des éléments. Cependant, l'algorithme souffrait encore de :

• Itération sur le dictionnaire dans un ordre non défini
• Marquage redondant des facteurs des nombres non premiers

Mise en œuvre de l'algorithme correct

Pour optimiser pleinement l'algorithme, une correction a été nécessaire :

1. Utiliser une liste au lieu d'un dictionnaire pour les indicateurs de primalité
2. Sauter les facteurs non premiers
3. Commencer le marquage des facteurs au carré du nombre premier, plutôt qu'à son double

L'Optimisé Algorithme

L'algorithme optimisé (primes_sieve2) utilise une liste de booléens pour les indicateurs de primalité. Il initialise la liste à True pour tous les nombres supérieurs à 1. Ensuite, il parcourt la liste en marquant les nombres non premiers :

def primes_sieve2(limit):
    a = [True] * limit                          # Initialize the primality list
    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

En optimisant ces aspects clés, l'algorithme améliore considérablement ses performances, trouvant amorce jusqu'à 2 millions en quelques secondes.

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!