Générateur de nombres premiers simples en Python
Ce code vise à générer une liste simple de nombres premiers, mais il n'imprime actuellement que le décompte , qu'un nombre soit premier ou non.
Le problème
Le code utilise une boucle imbriquée pour vérifier la divisibilité du compteur (compte) par les nombres de 2 à la racine carrée du nombre. Cependant, il suppose à tort que si un nombre n'est pas divisible par l'itération actuelle de la boucle interne, il doit être premier.
Le correctif
Pour résoudre ce problème , nous introduisons une variable booléenne, isprime, pour suivre le statut premier de count. Dans la boucle interne, si count est divisible par la valeur actuelle de x, nous définissons isprime sur False et rompons la boucle. Cela garantit que nous n'imprimons le nombre que s'il est véritablement premier.
Mise en œuvre optimisée
Bien que ce code fournisse une compréhension de base de la génération première, une approche plus efficace connue sous le nom de le Tamis d'Ératosthène peut être employé. Cette technique commence par supposer que tous les nombres sont premiers, puis parcourt la séquence, marquant les nombres non premiers comme composites.
Voici une implémentation hautement optimisée du tamis d'Eratosthène :
def gen_primes(): D = {} q = 2 while True: if q not in D: yield q D[q * q] = [q] else: for p in D[q]: D.setdefault(p + q, []).append(p) del D[q] q += 1
Ceci le code renvoie un générateur qui produit des nombres premiers. Il utilise un système de cartographie économe en mémoire pour suivre les composites et leurs témoins. Cette optimisation réduit considérablement le temps et les ressources de calcul nécessaires pour générer de grands nombres premiers.
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!