Dans cette vidéo, le présentateur explique comment concevoir un algorithme qui, à partir d’un entier N (>1) saisi par l’utilisateur, liste tous les nombres premiers inférieurs ou égaux à N. Il commence par rappeler la définition d’un nombre premier (exactement deux diviseurs distincts) puis décrit une première version naïve de l’algorithme : deux boucles imbriquées (une parcourant les entiers de 1 à N, l’autre testant chaque entier i contre tous les j de 1 à i, en comptant les diviseurs via l’opération modulo). Il détaille les variables utilisées (n, i, j, nbDiv) et la logique de validation de l’entrée avec une boucle « while »/« repeat ». Après avoir montré le code Python fonctionnel (affichage des premiers pour N=10, 100, etc.), il souligne son inefficacité pour de grandes valeurs (ex. N=1000) car la petite boucle continue même après que le nombre de diviseurs dépasse 2. Il introduit alors une optimisation : interrompre la petite boucle dès que nbDiv > 2 grâce à l’instruction break, ce qui réduit drastiquement le temps d’exécution (de ~5 s à ~1,5 s pour N=10000). Le présentateur exécute les deux versions, compare les temps et conclut que l’optimisation est cruciale, tout en rappelant que l’objectif principal est d’apprendre l’algorithmique plutôt que la syntaxe Python. La vidéo se termine par une invitation à la prochaine séance.
Chapters
Bonjour à tous et bienvenue dans cette nouvelle vidéo où nous allons traiter l'exercice suivant on souhaite créer un algorithme qui demande à l'utilisateur de saisir un entier supérieur à 1 et qui liste ensuite tous les nombres premiers inférieurs à ce nombre-là. Comme vous le savez déjà, un nombre premier est un entier naturel qui admet seulement 2 diviseurs distincts. Ses diviseurs sont 1 et le nombre lui-même. Par exemple, 5 est un nombre premier car il n'a que 2 diviseurs qui sont 1 et 5. Donc, si l'utilisateur saisit le nombre 10, on affichera à l'écran tous les nombres premiers inférieurs ou égaux à 10 et qui sont 2, 3, 5 et 7. Dans notre algorithme, nous allons commencer par lister tous les entiers positifs non nuls qui sont inférieurs ou égaux au nombre spécifié par l'utilisateur. Parmi les nombres de la liste, il y en a qui sont premiers et il y en a qui ne le sont pas. Nous devons donc procéder à leur filtrage en ne conservant que les nombres premiers. Nous allons ensuite lister pour chacun de ces nombres-là tous les entiers qui sont compris entre 1 et le nombre en question. Par exemple, pour le nombre 5 nous allons générer les nombres 1, 2, 3, 4 et 5. La prochaine étape consiste à essayer de diviser chaque nombre de la liste par le nombre listé devant lui. À la fin, on comptera combien de diviseurs existe-t-il pour le nombre en question. Si le nombre de diviseurs vaut 2, alors le nombre de la liste est premier, donc on l'affiche. Sinon, alors il ne l'est pas. On imagine alors qu'on aura besoin de 2 structures itératives imbriquées: une pour lister les entiers positifs inférieurs ou égaux à l'entrée de l'utilisateur, et l'autre pour lister les éventuels diviseurs pour chacun de ces entiers-là. Vu que le nombre d'itérations est connu à l'avance pour les 2 structures itératives, alors on va choisir la boucle Pour. Dans notre algorithme on aura besoin des variables suivantes: n qui reçoit la valeur saisie par l'utilisateur, i qui est le compteur de la grande boucle qui liste les entiers positifs inférieurs ou égaux à l'entrée de l'utilisateur, j qui représente le compteur de la petite boucle qui liste les éventuels diviseurs du nombre i courant, nbDiv qui représente le nombre de diviseurs dont le nombre i dispose. Toutes ces variables seront de type entier. Je propose l'algorithme suivant: dans le corps de l'algorithme, on demande à l'utilisateur de saisir un entier supérieur à 1 que l'on affecte à la variable n. Ces instructions sont placées dans la structure itérative Répéter qui va se réexécuter jusqu'à ce que la valeur entrée par l'utilisateur soit supérieure à 1. Ensuite, on lance la boucle Pour qui a comme compteur la variable i. Cette boucle va s'exécuter n fois et a pour mission de générer tous les entiers compris entre 1 et n. Pour chaque itération de cette grande boucle, on initialise la variable nbDiv à 0 pour dire que le nombre i courant n'a encore aucun diviseur. Ensuite, on lance la deuxième boucle dont le compteur est la variable j et qui va s'exécuter i fois en générant des diviseurs éventuels du nombre i courant. Ces nombres-là sont compris entre 1 et i. À l'intérieur de la petite boucle, on vérifie si i est divisible par j en exécutant l'opération modulo. Si le résultat vaut 0, alors j est un diviseur pour i. Dans ce cas, on incrémente la variable nbDiv de 1. À la fin de la petite boucle, on aura incrémenté la variable nbDiv autant de fois qu'il y a de diviseurs pour i. Avant de sortir de la grande boucle, on doit décider si on doit afficher le nombre i comme étant un nombre premier ou non. On procède donc à un traitement conditionnel qui vérifie si la variable nbDiv vaut 2, ce qui signifie que le nombre i courant a 2 diviseurs. Dans ce cas, on affiche la valeur de i. À la fin du traitement, on aura affiché tous les nombres premiers compris entre 1 et le nombre N. Cependant, notre algorithme n'est pas assez optimisé. En effet, imaginez que l'utilisateur a saisi la valeur 1000. On imagine donc qu'il y a beaucoup d'itérations à exécuter. Supposons que l'on est arrivé à l'itération de la grande boucle où i vaut 900 par exemple. Dans ce cas, à l'aide de la petite boucle on va générer tous les diviseurs éventuels compris entre 1 et 900, puis on va procéder aux calculs successifs du modulo pour vérifier si i est divisible par j. Or, quand on arrive à la valeur 3, on aura déjà compté 3 diviseurs pour le nombre 900 qui sont 1, 2 et 3. À ce stade on est sûr que 900 n'est pas premier, donc nous ne l'afficherons pas. Et pourtant, on continue à calculer i modulo j jusqu'à ce que j vaut 900. Vous imaginez donc qu'on a exécuté des centaines d'itérations inutilement, ce qui augmentera considérablement le temps d'exécution de notre algorithme. Pour pallier ce problème, on va interrompre prématurément la boucle Pour une fois que le nombre de diviseurs trouvés est supérieur à 2. Notre algorithme sera donc écrit comme ceci: Alors, après chaque incrémentation de la variable nbDiv, on vérifie si la valeur de celle-ci est supérieure à 2. Si c'est le cas, alors on interrompt la boucle courante. Notez que j'ai exprimé cette interruption avec un commentaire, mais dans de nombreux langages de programmation on utilise l'instruction break. Nous allons maintenant écrire notre algorithme à l'aide du langage Python pour voir si le résultat obtenu à l'aide de cet algorithme s'accorde bien avec ce qui est attendu. Alors notez que je vais pas trop expliquer la syntaxe du Python parce que l'objectif principal de cette série est d'apprendre l'algorithmique. Donc exceptionnellement pour cette séance, nous allons implémenter notre algorithme à l'aide d'un vrai langage de programmation pour voir comment il va se comporter. Donc la première opération, c'est qu'on va demander à l'utilisateur de saisir le nombre n, et bien sûr on va insister sur le fait que n doit être supérieur à 1. On mettra donc ici la structure while, c'est-à-dire que c'est une condition qui est toujours vraie, donc c'est comme si on a programmé une sorte de boucle infinie. On mettra ici n= input. Veuillez entrer un entier supérieur à 1. Et si c'est le cas, ça veut dire que l'utilisateur saisit une valeur qui est supérieure à 1, donc pas la peine de continuer la boucle. Alors on arrête en mettant break. On mettra donc ici if n est supérieur à 1, alors on met un break. Ensuite nous allons programmer la première boucle. Dans ce cas cette boucle va générer des nombres i qui sont compris entre 1 et n. Pour chaque itération de i on va initialiser nbDiv à 0. Ensuite on va programmer la deuxième boucle. Qui dans ce cas va générer des nombres j qui sont compris entre 1 et le i courant. Maintenant on va procéder au test, ça veut dire si i est divisible par j, dans ce cas on va incrémenter nbdiv de 1. Maintenant à la sortie de la boucle j, ça veut dire toujours à l'intérieur de la boucle i, on va vérifier la valeur de nb_div. Si c'est égal à 2, ça veut dire que le nombre i a 2 diviseurs, ce qui signifie qu'il est premier. On va donc l'afficher. Notez que je n'ai pas pris en considération l'arrêt prématuré de la boucle au cas où je trouve que le nombre de diviseurs est supérieur à 2, c'est-à-dire que c'est une version simplifiée de l'algorithme, mais bien sûr que l'on va améliorer juste après. Exécutons maintenant pour voir le résultat. Donc entrez un nombre entier supérieur à 1, par exemple on va mettre 10. Donc il affiche 2, 3, 5 et 7. Ça veut dire que le code maintenant marche bien. Maintenant supposons que j'ai entré une valeur qui est inférieure à 1. Par exemple 0. Donc le message se réaffiche, donc veuillez entrer un entier supérieur à 1. Quand on met par exemple -7, ça insiste, bon c'est-à-dire il faut vraiment qu'on entre une valeur qui est supérieure à 1 pour que ça marche. Quand je mets par exemple 100, donc ça affiche tous les nombres premiers qui sont inférieurs ou égaux à 100. Ce que je vais faire maintenant, c'est que je vais fixer la valeur de n, ça veut dire je vais pas demander à l'utilisateur de la saisir, donc je vais éliminer ces instructions et je mettrai juste par exemple n= 10000, c'est une valeur qui est relativement grande. Autrement dit, je vais essayer d'afficher tous les nombres premiers qui sont inférieurs ou égaux à 10000. Maintenant, je vais exécuter le code comme ceci pour voir ce que ça donne. J'exécute directement ici. Donc voilà, à la fin de l'exécution, il y a tous les nombres premiers qui sont inférieurs à 10000 qui ont été affichés et en plus j'ai le temps d'exécution. Ça veut dire que l'exécution de ce programme a pris un peu plus de 5 secondes. Maintenant on va intégrer l'instruction break qui va arrêter prématurément la boucle au cas où le nombre de diviseurs est supérieur à 2, que l'on va d'ailleurs ajouter ici. Donc si c'est supérieur à 2, pas la peine de continuer, on interrompt prématurément la boucle et on passe à la prochaine valeur de i. Exécutons maintenant pour voir. Donc maintenant l'exécution est faite en 1 seconde et demie. Le résultat c'est le même, mais on a considérablement gagné du temps à l'exécution. Alors maintenant vous constatez un petit peu l'utilité de l'arrêt prématuré de la boucle avec l'instruction break. Figurez-vous que je me suis pas trop arrêté sur l'explication du code Python parce que comme je l'ai dit tout à l'heure, l'objectif de cette série n'est pas la programmation en soi mais l'algorithmique, ça veut dire l'initiation à la programmation. Donc quel que soit le langage que vous utilisez, j'estime que c'est un bon choix tant que vous le maîtrisez, juste pour tester vos algorithmes pour voir si ça marche vraiment comme vous l'espérez. On se contente de ça pour cette séance. Merci pour votre attention et à la vidéo prochaine.
