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

Mary-Kate Olsen
Libérer: 2024-11-15 09:27:02
original
808 Les gens l'ont consulté

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. La boucle vérifie la divisibilité mais imprime incorrectement le décompte même si elle trouve un diviseur.
  2. L'instruction continue termine l'itération en cours mais doit être remplacé par break pour arrêter complètement la recherche lorsqu'un diviseur est trouvé.

Code amélioré :

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
Copier après la connexion

Explication :

  • La boucle externe incrémente le décompte pour tester le prochain nombre premier possible.
  • La boucle intérieure va maintenant jusqu'à la racine carrée du décompte, comme n'importe quel un diviseur supérieur à la racine carrée aura un diviseur correspondant en dessous de la racine carrée.
  • 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 décompte est premier et est imprimé.

Génération Prime Avancée :

Pour une génération première plus efficace, le 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
Copier après la connexion

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!

source:php.cn
Déclaration de ce site Web
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
Derniers articles par auteur
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal