Présentation de l'algorithme :
Le crible d'Erastothène.
Le programme donne la liste des nombres premiers inférieurs à Stop.
Stop est un entier donné par l'utisateur.
Ent est la liste de 2 à Stop des entiers. On affecte n à Ent[n]. Ent[0] et Ent[1] ne sont pas affectés.
Prim est la liste des nombres premiers, vide en début de traitement.
RangE et RangP indique le rang des termes en traitement.
A ce niveau, RangE est -1 et RangP est 2.
Début du traitement.
Boucle de lecture de Stop qui vérifie que Stop est un entier supérieur à 2.
Début boucle "tant que" RangE <= Stop
Boucle "tant que" qui cherche le premier nombre non nul de Ent avec incrémentation de RangE
On teste si RangE > Stop. Ce teste est nécessaire en fin de traitement quand tous les termes de Ent sont nuls.
Début Si
On affecte Ent[RangE] à Prim[RangP]
Une boucle met tous les multiples de Prim[RangP] à 0 dans Ent
Fin Si
Fin "tant que"
Affichage des nombres premiers.
Fin
Le programme a été testé jusqu'à 25777. Pour des centaines de mille, il plante. Dépassement de capacité dans les boucles.
Mais sur internet le programme s'arrète d'afficher aux environs de 3000.
Tester l'algorithme :
Graphique :
Code de l'algorithme :
1
VARIABLES
2
Ent EST_DU_TYPE LISTE
3
Prim EST_DU_TYPE LISTE
4
RangE EST_DU_TYPE NOMBRE
5
RangP EST_DU_TYPE NOMBRE
6
Stop EST_DU_TYPE NOMBRE
7
n EST_DU_TYPE NOMBRE
8
i EST_DU_TYPE NOMBRE
9
mult EST_DU_TYPE NOMBRE
10
DEBUT_ALGORITHME
11
Stop PREND_LA_VALEUR 0
12
//On met Stop à 0 pour entrer dans la boucle de lecture "Tant que Stop<2 ou non entier".
13
TANT_QUE (Stop<2 OU Stop!=floor(Stop)) FAIRE
14
DEBUT_TANT_QUE
15
AFFICHER "Entrez un nombre entier positif supérieur à 2 : "
16
LIRE Stop
17
AFFICHER Stop
18
FIN_TANT_QUE
19
//On recherche tous les nombres premiers inférieurs à Stop.
20
POUR i ALLANT_DE 2 A Stop
21
DEBUT_POUR
22
Ent[i] PREND_LA_VALEUR i
23
//Ent contient les entiers de 2 à Stop.
24
FIN_POUR
25
RangE PREND_LA_VALEUR 2
26
//2 est le premier terme de la liste Ent et aussi le plus petit nombre premier.
27
RangP PREND_LA_VALEUR -1
28
//L'incrémentation de RanP ce fait avant l'affectation donc le premier terme de Prim sera Prim[0]
29
//En fin de programme RangP sera le rang du dernier terme de Prim affecté.
30
TANT_QUE (RangE<=Stop) FAIRE
31
DEBUT_TANT_QUE
32
//Boucle qui se termine quand on a épuisé tous les termes de Ent
33
TANT_QUE (Ent[RangE]==0) FAIRE
34
DEBUT_TANT_QUE
35
//Cette boucle s'arrête dés qu'on rencontre un terme non nul.
36
RangE PREND_LA_VALEUR RangE+1
37
FIN_TANT_QUE
38
SI (RangE<=Stop) ALORS
39
DEBUT_SI
40
//A la fin du traitement, tous les termes Ent peuvent être nuls et RangE sera supérieur à Stop.
41
//Et le programme va planter. D'où la nécessité du test "Si".
42
RangP PREND_LA_VALEUR RangP+1
43
//Au premier passage, rangP sera donc 0.
44
Prim[RangP] PREND_LA_VALEUR Ent[RangE]
45
//La boucle suivante va mettre à zéro tous les multiples des nombres inférieurs à celui traité.
46
//Donc ce nombre n'est pas un multiple et il est premier. On l'affecte au premier terme vide de Prim.
47
n PREND_LA_VALEUR floor(Stop/Prim[RangP])
48
//n est le test d'arrêt de la boucle "Pour". C'est le quotient entier de Stop du nombre premier traité.
49
//Le plus grand multiple de Prim[RangP] contenu dans Ent est n*Prim[RangP].
50
POUR i ALLANT_DE 1 A n
51
DEBUT_POUR
52
//Mise à zéro de tous les termes Ent contenant des multiples Prim[RangP]
53
//mult est une variable auxiliaire pour alléger l'écriture.
54
// Les programmes sont sensibles et une formule trop compliqué peut être refusée ou le faire planter.
55
mult PREND_LA_VALEUR Prim[RangP]*i
56
Ent[mult] PREND_LA_VALEUR 0
57
FIN_POUR
58
FIN_SI
59
FIN_TANT_QUE
60
//Affichage en ligne des nombres premiers.
61
AFFICHER "Liste des nombres premiers inférieurs ou égaux à "
62
AFFICHER Stop
63
AFFICHER " : "
64
POUR i ALLANT_DE 0 A RangP
65
DEBUT_POUR
66
AFFICHER Prim[i]
67
AFFICHER " ; "
68
FIN_POUR
69
FIN_ALGORITHME