Maison >développement back-end >Tutoriel Python >Comment puis-je optimiser un générateur de nombres premiers simples en Python ?

Comment puis-je optimiser un générateur de nombres premiers simples en Python ?

Mary-Kate Olsen
Mary-Kate Olsenoriginal
2024-11-15 09:27:02897parcourir

How Can I Optimize a Simple Prime Number Generator in Python?

Optimisation d'un générateur de nombres premiers simples en Python

Le code Python fourni vise à générer des nombres premiers mais nécessite des améliorations pour plus d'efficacité.

Problèmes avec le code d'origine :

  1. Les vérifications de boucle pour la divisibilité mais imprime incorrectement le décompte même s'il trouve un diviseur.
  2. L'instruction continue termine l'itération en cours mais doit être remplacée par break pour arrêter complètement la recherche lorsqu'un diviseur est trouvé.

Amélioré Code :

import math

def main():
    count = 3
    while True:
        isprime = True
        for x in range(2, math.ceil(math.sqrt(count)) + 1):
            if count % x == 0: 
                isprime = False
                break
        if isprime:
            print(count)
        count += 1

Explication :

  • La boucle externe incrémente le décompte pour tester le prochain nombre premier possible.
  • La boucle intérieure s'étend désormais jusqu'à la racine carrée du décompte, car tout diviseur supérieur à la racine carrée aura un diviseur correspondant en dessous du carré racine.
  • Si le nombre est divisible par n'importe quel x, l'indicateur isprime est défini sur False et la boucle interne est interrompue.
  • Si aucun diviseur n'est trouvé, le nombre est premier et est imprimé .

Génération Prime avancée :

Pour une génération Prime plus efficace, le Un tamis d'Eratosthène est recommandé. Voici une implémentation Python optimisée avec commentaires :

def gen_primes():
    D = {}
    q = 2
    while True:
        if q not in D:
            yield q
            for later in range(q * q, 1000000, q):
                D[later] = [q]
        else:
            for later in range(q + D[q][0], 1000000, q):
                D.setdefault(later, []).append(q)
            del D[q]
        q += 1

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn