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

Optimisation de la génération de nombres premiers avec le tamis d'Eratosthène en Python

Le tamis d'Eratosthène est un algorithme reconnu pour identifier les nombres premiers jusqu'à une limite spécifiée. Bien que simple à mettre en œuvre, il peut être étonnamment lent pour des limites importantes.

Mise en œuvre lente

L'implémentation Python suivante du tamis fait face à des défis d'efficacité :

def primes_sieve(limit):
    primes = range(2, limit+1)

    for i in primes:
        factors = range(i, limitn, i)
        for f in factors[1:]:
            if f in primes:
                primes.remove(f)

Le goulot d'étranglement réside dans le redimensionnement continu de la liste des nombres premiers à mesure que les nombres sont supprimés. La suppression d'un élément d'une liste Python implique le déplacement des éléments suivants, ce qui en fait une opération coûteuse en termes de calcul.

Implémentation plus rapide à l'aide d'un dictionnaire

Pour résoudre ce problème, une implémentation basée sur un dictionnaire peut être utilisé :

def primes_sieve1(limit):
    primes = dict()
    for i in range(2, limit+1): primes[i] = True

    for i in primes:
        factors = range(i,limitn, i)
        for f in factors[1:]:
            primes[f] = False

Cela maintient un dictionnaire d'indicateurs de primalité, réduisant ainsi le besoin d'opérations de redimensionnement. Cependant, parcourir les clés du dictionnaire dans un ordre indéfini et marquer à plusieurs reprises les facteurs non premiers des nombres non premiers limite l'efficacité.

Algorithme corrigé avec liste

L'implémentation correcte suit de plus près l'algorithme Sieve d'Eratosthène :

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

Ceci maintient une liste d'indicateurs de primalité, initialisant tous les nombres comme premiers sauf 0 et 1. Il marque les multiples de nombres premiers comme non premiers, en commençant par le carré du premier pour optimiser le processus.

En résolvant les problèmes d'efficacité dans la mise en œuvre, cet algorithme a considérablement corrigé améliore la vitesse de génération des nombres premiers, même pour de grandes limites.

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!