Coder un algorithme qui détermine les nombres premiers.

Version imprimable

Bonjour/Bonsoir:
je suis actuellement en train de coder un algorithme permettant de déterminer les nombres premiers dans un intervalle (programme relativement simple) et j'ai utilisé comme brique de base une fonction que j'avais codé en C++:
Code:

1 2 3 4 5 6 7 8 vector<int>premier bool est_premier(int n) { for (int p = 0; p<prime.size(); ++p) if (n%prime[p]==0) return false; // no remainder: prime[p] divided return true; // no smaller prime could divide }
Cette fonction va tester des nombres donnés et indiquer s'ils sont croissants, j'ai tenté de la retranscrire en python (je dois rendre ce travail en python) et voilà ce que cela donne:
Code:

1 2 3 4 5 6 7 8 9 10 11 liste_premiers = [] def est_premier(n): p = 0 while p < len(liste_premiers): if n % liste_premiers[p] == 0: p = len(liste_premiers) return False # ce n'est pas un nombre premier return True #c'est un nombre premier
Puis je teste cette fonction dans un intervalle de 3 à 100 avec 2 considéré comme le plus petit nombre premier ( 1 est écarté).
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 liste_premiers.append(2) #le plus petit nombre premier i = 3 while i <= 100: #on veut connaître les nombres premiers de l'intervalle [3;100] if est_premier(i): liste_premiers.append(i) i+=1 print ("Nombres premiers:") for element in liste_premiers: print (element)
mais quand j'exécute le programme il me renvoie :
2
3
5
7
9
11 .... de deux en deux jusqu'à 99

J'en ai déduit que seule l'opération i % 2 était effectuée, je pense qu'il s'agit d'une erreur au niveau des return de la fonction "est_premier" (je me débrouille très mal en Python).

Pourriez-vous me donnez une piste de travail s'il vous plaît?
Merci d'avance!

PS (aux modérateurs): je n'avais aucune idée d'où mettre cette discussion, j'ai pensé que calcul scientifique serait le plus approprié...

Salut,

Citation:

Envoyé par Gwynbleidd

Pourriez-vous me donnez une piste de travail s'il vous plaît?

Relisez votre code:
Code:

1 2 3 4 5 6 7 8 liste_premiers = [] def est_premier(n): p = 0 while p < len(liste_premiers): if n % liste_premiers[p] == 0: p = len(liste_premiers) return False # ce n'est pas un nombre premier
Vous devez avoir une idée de ce qu'il devrait faire et pouvoir vérifier que ca le fait en insérant des "print" judicieux...

- W

Toutes mes excuses je n'ai pas sélectionné l'incrémentation de p dans le code,voilà ce que cela donne:

Code:

1
2
3
4
5
6
7
8
9
10
 
def est_premier(n):
    p = 0
    while p < len(liste_premiers):
        if n % liste_premiers[p] == 0:
            p = len(liste_premiers)
            return  False         # ce n'est pas un nombre premier
 
        return True               #c'est un nombre premier
    p+=1

Je viens à l'instant de rajouter des print:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
def est_premier(n):
    p = 0
    while p < len(liste_premiers):
        if n % liste_premiers[p] == 0:
            p = len(liste_premiers)
            print("Erreur")
            return  False         # ce n'est pas un nombre premier
 
        else:
            print ("ok")
            return True
                    #c'est un nombre premier
        p+=1

et il en ressort:
.
.
.
ok
Erreur
ok
Erreur
ok
Erreur
Nombres premiers:
2
3 .......

Je ne maîtrise pas bien les return, la fonction quitte-t-elle dès qu'un return est lancé? (car tous les nombres testés le sont avec i % 2).

10/02/2017, 13h45
wiztricks

Citation:

Envoyé par Gwynbleidd

Je ne maîtrise pas bien les return, la fonction quitte-t-elle dès qu'un return est lancé? (car tous les nombres testés le sont avec i % 2).

"return" fonctionne pareil qu'en C++.
Si vous avez des soucis avec ces bases là, je ne peux que vous recommander la lecture d'un tuto..

- W

J'avoue avoir encore du mal à les return mais j'ai lu le tutoriel et il m'a éclairé sur quelques points du python.
J'ai finalement légèrement modifié mon programme, je le poste au cas où quelqu'un serait interessé:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
 
import math
 
liste_premiers = []
 
def est_premier(n):
    compteur = 0
    p = 0
    while p < len(liste_premiers):
        if n % liste_premiers[p] != 0:                      #Si ce nombre est premier, alors il n'est pas divisible par les autres nombres premiers.
            compteur +=1
 
        p+=1
    if compteur == len(liste_premiers):                  #la fonction rajoute le nombre premier directement dans le tableau.
        liste_premiers.append(n)
 
try:    
    liste_premiers.append(2)    #le plus petit nombre premier
    i = 3
    while i <= 100:
            est_premier(i)                     
            i+=1
 
     print ("Nombres premiers:")                      #on affiche les nombres premiers jusqu'à 100.
 
    for element in liste_premiers:
                        print (element)
 
except:
        print("Error!")

Un grand merci à toi wiztricks pour ton aide patiente! :merci:

Sujet résolu!

Citation:

Envoyé par Gwynbleidd

J'ai finalement légèrement modifié mon programme, je le poste au cas où quelqu'un serait interessé:

oui enfin côté calcul des nombres premiers, vous avez des tas de code déjà écrits par Tyrtamos et d'autres qui sont bien meilleurs...

Pour ce qui est de Python:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
liste_premiers = []
 
def est_premier(n):
    compteur = 0
    p = 0
    while p < len(liste_premiers):
        if n % liste_premiers[p] != 0:                      #Si ce nombre est premier, alors il n'est pas divisible par les autres nombres premiers.
            compteur +=1
 
        p+=1
    if compteur == len(liste_premiers):                  #la fonction rajoute le nombre premier directement dans le tableau.
        liste_premiers.append(n)

pensez à la construction "for...else":

Code:

1
2
3
4
5
6
def est_premier(n):
        for p in range(len(liste_premiers)):
             if n % liste_premiers[p] == 0:
                   break            
        else:
             liste_premiers.append(n)

- W

11/02/2017, 12h51
Gwynbleidd

Effectivement votre code est plus propre, merci beaucoup,
en ce qui concerne le calcul des nombres premiers je travaille sur la rapidité de calcul des nombres premiers et cette version servait à montrer que cette méthode était lente (j'ai importé la librairie time), je vais rédiger un algorithme sur le crible d’Ératosthène plutôt.

Cordialement.