Crible d’Ératosthène

OShine · February 2020

Bonsoir,

Etant novice en python, je ne comprends rien au code suivant.
Surtout les lignes 1,2,3 et 7.

Ça veut dire quoi

premier=n * True

puis

premiers[0]=False

?

noobey · February 2020

si n = 5,

premiers = n * [True]

Alors

premiers = [True, True, True, True, True]

et

premiers[0] = False

donne alors après

[False, True, True, True, True]

Rescassol · February 2020

Bonjour,

Déjà, il faudrait recopier correctement:
"premier=n * True" n'est pas "premiers=n * [True]".
Cette ligne fabrique un tableau de n booléens égaux à True.

"premiers[0]=False" met False dans la première case du tableau.

Cordialement,

Rescassol

OShine · February 2020

Merci ! On
Mais je ne comprends pas la suite :

if premiers[p] :
print(p) :

Puis je ne comprends pas non plus

for i in range(p*p,n,p) :
premiers[ i]=False

[Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]

Rescassol · February 2020

Bonjour,

Ce n'est pas ce qui est écrit.
1) Il n'y a pas de ":" après le print(p)
2)Tu as oublié l'indentation.
3) Il manque "[ i]"

4) Si tu ne connais pas du tout le langage Python, on ne peut pas te l'apprendre en 3 messages, il faut te procurer un cours.

Cordialement,

Rescassol

Edit: Des typos ..............

noobey · February 2020

Juste... Est-ce que tu as au moins testé le code pour voir ce que faisaient ces commandes?

OShine · February 2020

C'est un programme simple, y a-t-il besoin d'apprendre Python de A à Z pour le comprendre ?
J'ai fait de la programmation en C, des choses bien plus compliquées.

Le programme j'ai testé il n'affiche rien. 95946

Rescassol · February 2020

Bonjour
Si tu as fait du C, tu devrais comprendre qu'écrire une fonction ne suffit pas, il faut l'appeler.
Crois-tu que fabriquer une bêche va suffire pour creuser un trou ? Il faut en plus t'en servir.
Cordialement,
Rescassol

noobey · February 2020

Tu dois connaitre les bases au moins. Et si tu faisais des choses si compliquées que ça en C, tu te demanderais pas ce que signifie la ligne

premiers[0] = True

qui est une commande de base de la programation, tous langages confondus

D'autant plus que tu es si fort en programmation en C que tu as oublié que pour afficher le résultat d'une fonction il faut appeler la fonction avant...Mais bon.

Math Coss · February 2020

Rescassol a écrit:

Crois tu que fabriquer une bêche va suffire pour creuser un trou ? Il faut en plus t'en servir.

Qu'est-ce que c'est, une bêche ?

OShine · February 2020

Ca ne marche toujours pas

def Eratosthène(n) :
  premiers=n*[True]
  premiers[0]=False
  premiers[1]=False
  for p in range (2,n):
    if premiers[p]:
      print (p)
      for i in range (p*p,n,p):
        premiers [ i]=False
 Eratosthène(100)

[Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]

OShine · February 2020

Je ne comprends pas la fin du programme à partir du if.

noobey · February 2020

"premiers =False"

Ce n'est pas ce qui est marqué... faut tout te corriger

Rescassol · February 2020

Bonjour,

Et d'autre part, l'indentation doit être de $4$ espaces.

Cordialement,

Rescassol

OShine · February 2020

Je n'ai pas compris quelle indentation choisir pour appeler la fonction.
Le programme tourne toujours à vide 95962

noobey · February 2020

1) Utilise ta touche tab pour faire une indentation (shift + tab pour l'enlever)
2) Erathostene(100) doit être écrit en dehors de la fonction donc en enlevant l'indentation.Sois propre, saute une ligne après la fonction et écris ton Erathostene(100) sans indentation

Rescassol · February 2020

Bonjour,

Les indentations sont toujours de $4$ espaces !!!
Par contre, si tu indentes l'appel, il est dans la fonction, et même pire ici, dans la boucle interne,ce qui n'est pas ce que tu veux.
Donc détente complètement l'appel.pour qu'il soit le programme principal.

Cordialement,

Rescassol

OShine · February 2020

Merci pour vos réponses ça marche enfin.

Par contre comme je n'ai pas trop compris le programme, quand je veux afficher le résultat en m'arrêtant à print(p) ça n'affiche rien. Est-ce normal ?

noobey · February 2020

Je ne comprends pas ce que tu veux dire

LEG · February 2020

tu as oublié la fin pour ("appeler ta fonction Eratosthène") écrire les nombres premiers P, exemple pour n = 300

n = 300
P = Eratosthène(n)

ce qui donne :

def Eratosthène(n):
    premiers = n*[True]
    premiers[0] = False
    premiers[1] = False
    for p in range(2,n):
        if premiers[p]:
            print(p)
            for i in range(p*p,n,p):
                premiers[ i] = False

n = int(input("donner la valeur de n : "))
P = Eratosthène(n)

résultat :
2
3
5
7
11
13
17
19
23
29
31
37
41
.
...etc
.
.
241
251
257
263
269
271
277
281
283
293
>>>

noobey · February 2020

Ecrire "P = Eratosthène(n)" au lieu de "Eratosthène(n)" ne change rien vu que la fonction n'a pas de return elle ne fait que printer un résultat à l'écran !

OShine · February 2020

LEG oui le programme tourne bien. Je ne comprends pas la partie rouge du code. J'ai essayé d'exécuter le programme jusqu'à "print(p)" mais ça n'affiche rien. Pourtant print veut bien dire afficher non ?

def Eratosthène(n):
    premiers = n*[True]
    premiers[0] = False
    premiers[1] = False
    [b][color=#FF0000]for p in range(2,n):
        if premiers[p]:[/color][/b]
            [b][color=#FF0000]print(p)
            for i in range(p*p,n,p):
                premiers[ i] = False[/color][/b]

noobey · February 2020

Normalement si tu exécutes la fonction jusqu'à print(p) tu printes tous les nombres de 2 à n-1. Pas très intéressant...

def Eratosthène(n):
    premiers = n*[True]
    premiers[0] = False
    premiers[1] = False
    for p in range(2,n):
        if premiers[p]:
            print(p)

Rescassol · February 2020

Bonjour,

Ce que tu viens de dire n'a pas de sens.
Que veut dire s'arrêter à print(p) ?
C'est l'appel du programme principal qui fait s'exécuter les choses.

Cordialement,

Rescassol

OShine · February 2020

Ok merci Rescassol

Ça veut dire quoi

premiers [p]

? Je n'ai pas compris cette commande.

noobey · February 2020

Mais OSHINE on t'a dit 1000 fois qu'il faut appeler la fonction après l'avoir définie, tu es bouché ou quoi?
Tu as fait de la programmation ou pas?

Accessoirement, premiers[p] est un booléen qui vaut True ou False, si True tu rentres dans la condition, sinon tu n'y rentres pas

Rescassol · February 2020

Bonjour,

premiers[p] n'est pas une commande, c'est la case numéro p du tableau premiers, exactement comme en en C.

Cordement,

Rescassol

OShine · February 2020

Ok merci oui désolé je suis rouillé :-(

Je vais réfléchir aux dernières ligne du programme.

LEG · February 2020

pour imprimer tes nombres premiers il faut l'instruction

print (p) à la condition que p soit définis par exemple P = premiers :
et non pas dans le programme sous la fonction:
if premier [P]: # ça veut dire si le nombre est premiers [P]
print(p) # il doit l'écrire en mémoire

là, je suppose, qu'il écrit en mémoire les nombres premiers [True] qu'il a trouvé , pour ensuite les restituer à la demande
# à l'appel de la fonction #:
P = Eratosthène(n) # là on appelle les nombres premiers [True = vraie]pour les imprimer; le programme est fini...

Je ne suis pas du tout programmeur, je n'y connais même rien... en général. Sauf un peu sur les crible d'Ératosthène... parce que j'en ai construit et fait programmer. Donc il me fallait bien savoir ce que font les différentes parties du programme et leur fonction....

lourrran · February 2020

premiers est un tableau, avec plein de valeurs. premiers[p] est la valeur de rang p ( Attention : le 1er élément porte ne n° 0 )

premiers est un tableau, et les valeurs qu'on peut avoir dans ce tableau, c'est True ou False ( Vrai ou Faux). C'est donc un tableau de booléens.

L'instruction if premiers[p] : peut paraître bizarre. En principe, dans une instruction, il y a un verbe, et ici, il n'y a pas de verbe. Habituellement , on dit : si Paul est plus grand que Pierre alors , ou encore si x est égal à 3 alors

Et ici, on dit un truc du genre : si x alors ( le symbole deux-points peut être traduit par alors )
C'est un raccourci ; la phrase complète est : si x=Vrai alors ou encore : if premiers[p]=True :

Donc à chaque fois que tu vois un IF sans symbole < ni > ni = sur la ligne, tu peux considérer qu'il faut ajouter =True pour compléter la ligne.

Il y a une logique derrière ça, c'est tout à fait normal que ce raccourci soit accepté... mais on ne va pas entrer dans cette discussion.

Rescassol · February 2020

Bonjour,

Le même programme légèrement modifié, tu n'as qu'à copier/coller:

def Eratosthene(n):
    Tab=[]
    premiers=n*[True]
    premiers[0]=premiers[1]=False
    for p in range(2,n):
        if premiers[p]:
            Tab.append(p)
            for i in range(p*p,n,p):
                premiers[ i]=False
    return Tab
    
T=Eratosthene(1000)    
print(T)

Cordialement,

Rescassol

OShine · February 2020

@Lourran
Ok merci et donc si la valeur est False premiers[p] n'affiche pas cette valeur False du tableau ?

OShine · February 2020

@Rescassol.
En effet, votre programme donne quelque chose de plus joli.
Après je vais m'acheter un bouquin de Python pour connaitre les commandes j'essaie juste d'avancer un peu sur le programme car le CAPES arrive bientôt.

OShine · February 2020

J'ai une question.
Le livre dit que si $p^2 \geq n$ on peut arrêter l'algorithme.

Mais il faut ajouter quoi comme commande pour l'arrêter ?

Poirot · February 2020

Bah tu peux arrêter ta boucle à la partie entière de $\sqrt n$ au lieu de $n$.

OShine · February 2020

D'accord merci.

OShine · March 2020

Je reviens sur ce sujet, je pense ne pas avoir compris la commande

for i in range(p*p,n,p)

Par exemple, si $n=20$ et $p=2$ que fait cette commande ?

Math Coss · March 2020

range(4,20,2)

est la liste des entiers obtenue en partant de 4, en allant de 2 en 2, et en continuant tant que l'entier est <20. C'est donc :

>>> range(4,20,2)
[4, 6, 8, 10, 12, 14, 16, 18]

Si on le met dans une boucle, cela fait parcourir à i toutes les valeurs de la liste précédente et exécuter pour chaque valeur la ou les instructions qui suivent. La syntaxe complète est :

for i in range(p*p,n,p):
    < une instruction ou un bloc d'instructions où i intervient sans doute >

OShine · March 2020

Merci ! Je viens de comprendre la logique.

En effet, si $p$ est premier on doit barrer tous les multiples stricts de $p$.

Pour $p=2$ les multiples sont $2 \times 3=6 = 2^2+2$ puis $2 \times 4 =8=2^2+2+2$ puis $2 \times 5 =10=2^2+2+2+2$

lourrran · March 2020

C'est vrai, mais tu as pris comme exemple p=2. Or p=2 est très mal choisi, il ne permet pas de voir toute la subtilité du truc.

Prenons comme exemple p=13, et prenons n=500 pour avoir un peu plus de données.
la boucle for i in range(p*p,n,p) va donner :
i=169 , puis i=182 , 195, 208 etc etc et on va dire pour tous ces nombres : ces nombres ne sont pas premiers.

On commence à 13*13=169 ; inutile de commencer par 13*2 ou 13*3 ou 13*4 ou ... . Pourquoi ? Parce qu'on a l'assurance que tous les multiples de 2 ou 3 ou 4 ont déjà tous le flag 'Faux'

Et dans ta liste des multiples de 2 qui sont traités, tu n'as pas parlé du 1er d'entre eux : 2²

OShine · March 2020

Bien vu Lourran en effet !

Crible d’Ératosthène

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 28