On se propose de mettre au point un programme pour calculer tous les nombres premiers inférieurs à un nombre N fixé.
On se propose de procéder ainsi :
1. On commence par générer une liste d’entiers non soulignés L := [2, 3, 4, . . ., N] ;
2. Ensuite, tant qu’il existe des nombres non soulignés dans la liste L :
(a) on souligne le plus petit nombre k de L non encore souligné ;
(b) pour tout nombre R > k de la liste L :
– si k est un diviseur de R, alors on supprime l’élément R de la liste ;
3. La liste L – qui contient maintenant exclusivement des nombres soulignés – est la liste des nombres premiers inférieurs à N.
Par exemple, si on applique cet algorithme pour N = 30, on obtient successivement les valeurs de L suivantes :
[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],
[2,3,5,7,9,11,13,15,17,19,21,23,25,27,29],
[2,3,5,7,11,13,17,19,23,25,29 ],
[2,3,5,7,11,13,17,19,23,29 ],
[2,3,5,7,11,13,17,19,23,29 ],
[2,3,5,7,11,13,17,19,23,29 ],
[2,3,5,7,11,13,17,19,23,29 ],
[2,3,5,7,11,13,17,19,23,29 ],
[2,3,5,7,11,13,17,19,23,29 ],
[2,3,5,7,11,13,17,19,23,29 ],
[2,3,5,7,11,13,17,19,23,29 ].
Travail demandé :
Deux programmes à réaliser:
I. Version statique
— Le programme doit définir une constante N de valeur prédéfinie (sur 2 octets).
— Le programme doit également réserver N-1 octets à partir d’une adresse Tab et un mot de 2 octets à l’adresse Pges qui va contenir le plus grand élément souligné (c’est à dire le dernier nombre souligné).)
— Cette suite de N octets peut être vue comme un tableau. Celui-ci est utilisé pour mémoriser les nombres effacés pendant l’exécution de l’algorithme
— Le programme doit afficher la trace de l’exécution (comme dans l’exemple)
II. Version Dynamique
Améliorer le programme pour faire en sorte qu’il fonctionne pour des valeurs de N non fixées. L’utilisateur du programme saisit sur l’entrée standard une valeur pour N et le programme doit afficher tous les nombres premiers inférieurs à N.
Votre programme doit utiliser les fonctions suivantes pour accéder au tableau :
Une fonction effacer qui prend en argument un nombre i et positionne la case correspondante du tableau Tab à 0, signifiant que le nombre i est effacé.
Une fonction marquer qui prend en argument un nombre i et positionne la case correspondante du tableau tab à 1, signifiant que le nombre i n’est pas effacé.
Une fonction lire qui prend en argument un nombre i et retourne dans EAX la valeur de la case correspondante dans le tableau Tab. Une fonction initialiser qui positionne tous les octets du tableau tab à 1. Cette fonction doit aussi positionner la variable Pges à la valeur 0 pour spécifier qu’aucun nombre du tableau n’est souligné.
Vous devez remettre une copie de votre Projet en Visual Studio avec le code clairement commenté. Un document de 5 pages au maximum expliquant l’implémentation de votre deux programmes
Partager