Comment optimiser l'impression de nombres premiers en Python pour des résultats précis ?

Impression de séries de nombres premiers en Python

L'identification des nombres premiers est un concept fondamental en mathématiques et en programmation. Un nombre premier est un entier supérieur à 1 qui n’est pas le produit de deux entiers plus petits. Le code Python suivant vise à imprimer une série de nombres premiers de 1 à 100.

Code et problème

Une approche courante pour trouver des nombres premiers consiste à parcourir les nombres de 2 à n. Pour chaque nombre, vérifiez s'il est divisible par un nombre compris entre 2 et lui-même (sauf 1). S'il est divisible, ce n'est pas un nombre premier ; sinon, c'est le cas.

Considérez le code suivant destiné à imprimer des nombres premiers entre 1 et 100 :

<code class="python">for num in range(1, 101):
    for i in range(2, num):
        if num % i == 0:
            break
        else:
            print(num)
            break</code>

Cependant, ce code rencontre un problème où les nombres impairs sont imprimés au lieu des nombres premiers. Le défaut survient parce que la boucle externe parcourt non seulement les nombres premiers mais également les nombres composés (multiples d’autres nombres). Par conséquent, la condition if num % i != 0 devient vraie pour les nombres composés impairs comme 9, conduisant à l'impression erronée de tous les nombres impairs.

Solution et optimisation

Pour corriger cela, nous devons modifier le code pour vérifier explicitement les nombres premiers. Voici la version révisée :

<code class="python">for num in range(2, 101):  # Start at 2 as 1 is not prime
    prime = True
    for i in range(2, num):
        if num % i == 0:
            prime = False
    if prime:
        print(num)</code>

Dans ce code, nous introduisons une variable booléenne prime, initialement définie sur True. Nous vérifions ensuite chaque nombre entre 2 et num-1 (hors num) en utilisant la boucle interne. Si num est divisible par n'importe quel nombre i, nous définissons prime sur False, indiquant qu'il n'est pas premier. Après la boucle interne, si prime reste vrai, nous imprimons num.

Ce code identifie avec précision les nombres premiers dans la plage spécifiée. Cependant, il peut être encore optimisé en vérifiant uniquement les diviseurs jusqu'à la racine carrée de num. En effet, tout facteur supérieur à la racine carrée aurait un facteur correspondant inférieur à la racine carrée.

Voici la version optimisée :

<code class="python">for num in range(2, 101):
    prime = True
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            prime = False
    if prime:
        print(num)</code>

En utilisant ces ajustements, le code imprime efficacement la série de nombres premiers compris entre 1 et 100.

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!