Comment l'algorithme du tamis d'Eratosthène peut-il être optimisé pour une génération plus rapide de nombres premiers ?

Le tamis d'Ératosthène

Le tamis d'Ératosthène est un algorithme ancien, mais il est encore utilisé aujourd'hui comme un moyen simple et efficace de trouver tous les nombres premiers inférieurs à un nombre donné. . L'algorithme fonctionne en marquant de manière itérative les multiples de chaque nombre premier, en commençant par 2.

Voici une implémentation Python du Tamis d'Ératosthène :

def sieve_of_eratosthenes(n):
    """Return a list of all prime numbers below n."""

    # Create a list of all numbers from 2 to n.
    numbers = list(range(2, n + 1))

    # Iterate over the numbers in the list.
    for i in range(2, int(n ** 0.5) + 1):

        # If the number is prime, mark off all its multiples.
        if numbers[i] != -1:
            for j in range(i * i, n + 1, i):
                numbers[j] = -1

    # Return the list of prime numbers.
    return [i for i in numbers if i != -1]

Cet algorithme est relativement simple à mettre en œuvre, et c'est assez efficace. Par exemple, il peut trouver tous les nombres premiers inférieurs à 1 million en 0,1 seconde environ sur un ordinateur moderne.

Complexité temporelle

La complexité temporelle du tamis d'Ératosthène est O(n log log n) . Cela signifie que l'algorithme prend un temps O(n) pour créer la liste de tous les nombres de 2 à n, et il faut un temps O(log log n) pour marquer tous les multiples de chaque nombre premier.

Peut-il être rendu encore plus rapide ?

Il existe plusieurs façons de rendre le tamis d'Ératosthène encore plus rapide :

• Utilisez un plus structure de données efficace. La liste de tous les nombres de 2 à n peut être stockée dans une structure de données plus efficace, telle qu'un vecteur binaire. Cela peut réduire les besoins en espace de l'algorithme et améliorer ses performances.
• Utilisez un algorithme de marquage plus efficace. L'algorithme permettant de marquer tous les multiples de chaque nombre premier peut être rendu plus efficace en utilisant une roue tamiseuse. Cela peut réduire la complexité temporelle de l'algorithme à O(n).
• Paralléliser l'algorithme. L'algorithme peut être parallélisé pour tirer parti de plusieurs cœurs sur un ordinateur moderne. Cela peut encore améliorer les performances de l'algorithme.

Voici une implémentation Python d'une version plus rapide du tamis d'Eratosthène :

import numpy as np

def sieve_of_eratosthenes_fast(n):
    """Return a list of all prime numbers below n."""

    # Create a bit vector to store the prime numbers.
    primes = np.ones(n // 2 + 1, dtype=np.bool)

    # Mark off all the multiples of 2.
    primes[3::2] = False

    # Iterate over the odd numbers from 3 to n.
    for i in range(3, int(n ** 0.5) + 1, 2):

        # If the number is prime, mark off all its multiples.
        if primes[i // 2]:
            primes[i * i // 2::i] = False

    # Return the list of prime numbers.
    return [2] + [2 * i + 1 for i in range(1, n // 2 + 1) if primes[i]]

Cet algorithme est plus rapide que la version originale du Tamis d'Ératosthène, et il peut trouver tous les nombres premiers inférieurs à 1 million en 0,01 seconde environ sur un ordinateur moderne.

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!