Quel est le moyen le plus rapide de trouver tous les nombres premiers inférieurs à un nombre entier N donné ?

Le moyen le plus rapide de lister tous les nombres premiers inférieurs à N

Cet extrait de code donne une implémentation Python d'une méthode pour générer efficacement une liste de nombres premiers jusqu'à un entier donné.

    def get_primes(n):
        numbers = set(range(2, n + 1))
        primes = []
        while numbers:
            p = numbers.pop()
            primes.append(p)
            numbers.difference_update(set(range(p * p, n + 1, p)))
        return primes

Temps Complexité :

La complexité temporelle du code donné est O(n log log n), car il utilise le tamis d'Eratosthène pour calculer les nombres premiers.

Notes d'implémentation :

• Le code initialise un ensemble de nombres contenant tous les entiers de 2 à n.
• Il supprime de manière itérative les nombres non premiers des nombres en marquant comme composites tous les multiples du plus petit nombre qui n'a pas encore été marqué. Ces multiples sont ignorés en parcourant le nombre premier actuel lors de la mise à jour des nombres.
• Le code s'arrête lorsque les nombres sont vides, et la liste des nombres premiers trouvés est renvoyée en nombres premiers.

Problèmes potentiels :

Il existe un problème potentiel avec la mise en œuvre où il marque le nombre de départ comme un nombre premier alors qu'il ne devrait prendre en compte que les nombres. de 2 à n. Cela pourrait être corrigé en démarrant la boucle à partir de 2 au lieu de 0.

Utilisation :

Pour utiliser cette implémentation, vous pouvez appeler la fonction get_primes et transmettre la valeur supérieure souhaitée lié comme argument. Par exemple, pour trouver tous les nombres premiers jusqu'à 1000, vous pouvez utiliser :

primes = get_primes(1000)

Sortie :

La sortie du code sera une liste de nombres premiers nombres jusqu’à l’entier spécifié. Par exemple, exécuter le code avec n = 1000 produira le résultat suivant :

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ..., 977]

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!