Crible d'ératosthène

[Nourita]

Bonjour,
Ecrire une procédure def crible(n) qui utilise le crible d'ératosthène pour afficher tous les nombres premiers inférieurs à une valeur n passé comme argument.
On s'attachera à respecter l'esprit de cette technique, et en particulier à éviter les multiplications, divisions et racines carrées, difficiles à effectuer pour les mathématiciens grecs.

[siger]

bonjour

voir sur Wikipedia:"crible d'Erathostene"

[WillyCagnes]

voir ce lien
http://www.math93.com/index.php/histoire-des-maths/notions-et-theoremes/186-crible-d-eratosthene

[Nourita]

Bonjour,
je n'est rien trouver dans wikipedia.
moi, je veux une programmation en python de crible d'ératosthène.

[Nourita]

merci beaucoup,

[Ben314]

Salut,
comme je sais pas quoi faire, je te propose une version légèrement plus compliquée de l'algo. (mais sans multiplications) :

Saisir(N)
Créer un tableau A[1..N+5]
A[1]=0; A[2]=1; A[3]=1; I=4;
Tant que I<=N faire
A[I]=0; I=I+1; A[I]=1; I=I+1; A[I]=0; I=I+1; A[I]=1; I=I+1; A[I]=0; I=I+1; A[I]=0; I=I+1;
P=5; PP=25; PS=2;
Tant que PP<=N faire
P2=P+P; P4=P2+P2; I=PP; IS=PS;
Tant que I<=N faire
A[I]=0;
Si IS=2 Alors I=I+P2; IS=4;
Sinon I=I+P4; IS=2;
Répéter
Si PS=2 Alors PP=PP+P4+4; P=P+2; P4=P4+8; PS=4;
Sinon PP=PP+P4+P4+16; P=P+4; P4=P4+16; PS=2;
Jusqu'à ce que A[P]=1

[Nourita]

cette programmation est très compliquée.

[paquito]

Je te donnes un programme écrit sur une calculatrice TI 82, mais où on est obligé de mettre les nombres premiers trouvés dans les liste statistiques L1(K), ce qui entraîne un temps d'exécution infernal;si ce programme est adaptable en langace python, ça devrait être beaucoup mieux.

rompt N
:effListe L1
:2->I
:2->L1(1)
:3->L1(2)
:5>p
:Lbl 1
:For(K,2,I)
:If L1(K)
:If ent(P/lL1(k)=P/L1(K)
:Then
:If P N
:Then
+2->P
:Goto 1
:End
:End
:End
:IfP N
:Then
:I+1->I
->L1(I)
:End
:If P N
:Then
:Goto1
:End

Ce programme qui a été difficile a réaliser met une minute et demi pour trouver les nombres premiers <100 et se bloque pour N=335; sans la possibilité de sortir de la boucle par un Goto, il était irréalisable; peut être qu'en python on peut faire beaucoup mieux?

[Ben314]

Eh ben, 1'30'' pour les cent premiers nombres premiers.... Vive le progrès..
A mon avis, je vais plus vite à la main (rappelons que, vu que 11²>100, il suffit d'enlever de la liste les multiples de 2, 3, 5 et 7 et que, comme 7*15>100, les seuls multiples de 7 à enlever sont 7²=49 et 7.13=91...)

Et, sinon, je rapelle que l'objectif était de se placer le plus proche possible de ce qu'aurait fait "un mathématicien grec" et je suis sûr qu'un matheux grec n'aurais jamais calculé je ne sais pas combien de racines carrés (ce que fait ton algo.) et encore moins calculé des parties entière de fractions comme P/L1(k).
L'algo. du crible ne demande AUCUNE division (entière ou réelle) ni vraiment de calculs de produit vu que le seul produit qu'on a à calculer c'est du P*P, et comme il faut le faire de proche en proche, on peut faire comme on le ferait à la main si on devait faire la table des carrés des entiers, c'est à dire en sommant les nombres impairs pour obtenir les carrés successifs.

[zygomatique]

Salut,
comme je sais pas quoi faire, je te propose une version légèrement plus compliquée de l'algo. (mais sans multiplications) :

Saisir(N)
Créer un tableau A[1..N+5]
A[1]=0; A[2]=1; A[3]=1; I=4;
Tant que I<=N faire
A[I]=0; I=I+1; A[I]=1; I=I+1; A[I]=0; I=I+1; A[I]=1; I=I+1; A[I]=0; I=I+1; A[I]=0; I=I+1;
P=5; PP=25; PS=2;
Tant que PP<=N faire
P2=P+P; P4=P2+P2; I=PP; IS=PS;
Tant que I<=N faire
A[I]=0;
Si IS=2 Alors I=I+P2; IS=4;
Sinon I=I+P4; IS=2;
Répéter
Si PS=2 Alors P=P+2; PP=PP+P4+4; PS=4;
Sinon P=P+4; PP=PP+P4+P4+16; PS=2;
Jusqu'à ce que A[P]=1

salut

pourrais-tu nous donner l'idée générale, le principe que tu utilises s'il te plait ?

merci par avance ...

:we:


j'aurais pensé plutôt à ça

saisir N
créer le tableau A[1, N]
créer le tableau B[1, N]
For I = 1 To N
...... A[I] = I ; B[I] = 1
B[1] = 0
I = 1
While I =< N
.....While B[I] = 0 And I < N
........... I = I + 1
.....J = I + I
.....While J =< N
..........B[J] = 0 ; J = J + I
.....I = I + 1
For I = 1 To N
....If B[I] = 1 Then Write A[I]


en fait le tableau B peut être remplacé par un tableau booléen


je n'utilise pas de multiplication non plus et respecte l'esprit de l'époque ....

N = 500 en moins de 2mn .... :lol3:

(et je pourrais faire mieux en éliminant d'office les multiples de 2 lors du remplissage des tableaux puis en commençant à i = 3 et en allant de 2 en 2 ...)

[paquito]

Eh ben, 1'30'' pour les cent premiers nombres premiers.... Vive le progrès..
A mon avis, je vais plus vite à la main (rappelons que, vu que 11²>100, il suffit d'enlever de la liste les multiples de 2, 3, 5 et 7 et que, comme 7*15>100, les seuls multiples de 7 à enlever sont 7²=49 et 7.13=91...)

Et, sinon, je rapelle que l'objectif était de se placer le plus proche possible de ce qu'aurait fait "un mathématicien grec" et je suis sûr qu'un matheux grec n'aurais jamais calculé je ne sais pas combien de racines carrés (ce que fait ton algo.) et encore moins calculé des parties entière de fractions comme P/L1(k).
L'algo. du crible ne demande AUCUNE division (entière ou réelle) ni vraiment de calculs de produit vu que le seul produit qu'on a à calculer c'est du P*P, et comme il faut le faire de proche en proche, on peut faire comme on le ferait à la main si on devait faire la table des carrés des entiers, c'est à dire en sommant les nombres impairs pour obtenir les carrés successifs.

Salut Ben,

J'ai juste fait, ça pour voir si c'était possible de faire un truc qui ressemble un peu au scribble avec la TI 82 qui est de très loin la calculatrice la plus répandue au lycée; de toute façon, on à le choix entre ça et algobox!

A titre d'information, à partir du bac 2018, les candidats devront être munis d'une calculatrice où l'on bloquera l'accès aux programmes où sont stockés tous les résultats de cours (maths, physique, , biologie); une vraie révolution! Ca veut dire aussi qu'il sera toujours question de compléter un petit bout d'algorirthme!

Quant à mon programme, c'est plus que décevant (je pourrais quand même écrire (L1(K))^2 \leq P)
et pour N=100 il ne teste que la divisibilité par 3, 5 ou 7 mais met bien 1 mn et demi et j'ai épuisé la mémoire au bout de 100 nombres premiers; totalement inutilisable!

[Ben314]

L'algorithme çi dessus utilise quelques petites "astuces" qui sont précisément celle que tout matheux faisant les calculs "à la main" utiliserait :

1) Une fois qu'on a dit que 2 et 3 sont premiers, les autres sont de la forme 6k-1 ou 6k+1 : ce qui explique la façon dont le tableau A est initialisé et le fait que, lorsqu'on passe au P suivant, on ajoute soit 2 (pour passer de 6k-1 à 6k+1), soit 4 (pour passer de 6k+1 à 6(k+1)-1) on fait évidement une fois sur deux +2 et une fois sur deux +4 (donc il faut une variable pour savoir où on en est qui est PS).

2) Plutôt que de (re)calculer P² à chaque itération, ce qui est très chiant à la main, il vaut mieux se servir du fait qu'on connaissait déjà le carré du P précédent (donc il faut une variable contenant le carré de P, qui est PP).
On utilise alors ce qu'on ferait à la main, à savoir (P+2)²=P²+4P+4 et (P+4)²=P²+8P+16 pour avoir la nouvelle valeur de P².

3) Une fois qu'on a repéré un nouveau nombre premier P, normalement, il faut barrer de la liste les multiple de P, c'est à dire les nombre de la forme I=m.P. Sauf que, si m est divisible par un nombre premier P'<P alors le nombre m.P a déjà été barré de la liste au moment où on a barré les multiples de P'.
En particulier, si m<P le nombre I=m.P a forcément déjà été barré de la liste et il suffit donc de commencer à m=P, c'est à dire à I=P.P=P² (ce que fait aussi l'algo. du lien de WillyCagnes). Enfin, il est inutile de barrer les nombre de la forme m.P avec m multiple de 2 ou de 3 vu qu'ils ont déjà été barrés donc on peut se contenter d'étudier les m de la forme 6k-1 ou 6k+1. Comme on passe d'un tel m au suivant en ajoutant 2 ou 4, c'est qu'on passe du dernier barré I=m.P au suivant en ajoutant 2P ou 4P (une fois sur 2).

Si on veut légèrement simplifier le programme, on peut ne considérer comme "cas particulier" de départ que les multiples de 2. Ca donnerais :

Saisir(N)
Créer un tableau A[1..N+1]
A[1]=0; A[2]=1; I=3;
Tant que I<=N faire
A[I]=1; I=I+1; A[I]=0; I=I+1;
P=3; PP=9;
Tant que PP<=N faire
P2=P+P; P4=P2+P2; I=PP;
Tant que I<=N faire
A[I]=0; I=I+P2;
Répéter
PP=PP+P4+4; P=P+2; P4=P4+8;
Jusqu'à ce que A[P]=1

Voire même ne pas faire de "cas particulier" du tout, mais c'est un peu con vu que le programme est pratiquement le même que çi dessus :


Saisir(N)
Créer un tableau A[1..N]
A[1]=0; I=2;
Tant que I<=N faire
A[I]=1; I=I+1;
P=2; PP=4;
Tant que PP<=N faire
I=PP;
Tant que I<=N faire
A[I]=0; I=I+P;
Répéter
PP=PP+P+P+1; P=P+1;
Jusqu'à ce que A[P]=1

[Ben314]

[quote="zygomatique"]saisir N
créer le tableau A[1, N]
créer le tableau B[1, N]
For I = 1 To N
...... A[I] = I ; B[I] = 1
B[1] = 0
I = 1
While I =N (ça, c'est écrit explicitement dans absolument toutes les description du crible vu que ça fait "trés beaucoup" accélérer le programme : on remplace une boucle de 1 à N par une boucle de 1 à racine(N))

Essaye le dernier que j'ai mis et compare le temps de calcul pour N=1000 par exemple...

[zygomatique]

ha oui merci ....

oui j'avais bien vu le +2 /+4 .... je l'avais utilisé avec mes spe pour tester la primalité d'un entier après avoir testé 2 et 3 .... et donc ensuite ne regarder que les entiers de la forme 6p +/- 1 comme éventuel diviseur ....

mais je n'avais pas bien vu cette histoire de carré effectivement .... pour s'arrêter à la racine carrée .... et le calcul du carré "du suivant" ...

et bien sur ouais inutile d'avoir deux listes .... en fait ....




oui en fait je n'ai pas essayé de faire un traitement particulier de 2 (et de 3 éventuellement) .... ni de m'arrêter à racine(n) .... qui en pratique ne répondent qu'à des considérations de vitesse d'exécution ...( non négligeable bien sur suivant les machines) ...


merci ....

:lol3:

[Robic]

moi, je veux une programmation en python de crible d'ératosthène.

Est-ce que tu connais l'algorithme du crible ? Est-ce que par exemple tu saurais le faire à la main ? Je pose cette question pour savoir où tu bloques : au niveau de l'algorithme ou de sa mise en oeuvre ?

Si tu connais l'algorithme, il reste à le programmer en Python. J'ai commencé à apprendre ce langage récemment (il y a un peu plus d'un mois) donc je ne suis pas du tout expert, mais je propose d'utiliser une liste.

- Soit tu crées une liste avec les nombres de 2 à N et tu effaces les multiples de 2, puis de 3, puis de 5, etc. (multiples calculés par addition) de la liste. Mais du coup on ne connaît pas le nombre d'après son indice dans la liste, donc il faut faire un test. À la fin, les éléments qui restent dans le tableau sont les nombres premiers.

- Soit tu crées une liste avec des booléens initialisés à False, le booléen de l'élément n° k indique si k est premier ou non. Cette fois on balaie les multiples pour les passer à True. À la fin, les éléments étant True sont les nombres premiers.

[Nourita]

Bonjour,
j'ai des difficultés au niveau de créé un algorithme.