Afficher tous les nombres premiers inférieurs à un nombre donné

Enoncé
Ecrire un programme qui lit un entier n et affiche tous les nombres premiers inférieurs à n.

Solution
Dans cet exercice, l'enseignant tente de compliquer les choses pour pousser les étudiants à utiliser une boucle à l'intérieur d'une autre. C'est un autre exercice classique que nous rencontrons dans la majorité des livres d'introduction à l'algorithmique.

Le programme qui vérifie si un nombre donné est premier est expliqué ici.

Tous ce qui reste à faire c'est de parcourir les valeurs inférieurs à "n" et de tester pour chaque nombre est ce qu'il est premier ou pas.

Le code sera ainsi :

Program Premiers;

Var 
 n, i, j : Integer;
 diviseur : Boolean;

Begin
 
 WriteLn('Donnez la limite n : ');
 ReadLn(n);
 
 WriteLn('Les nombres premiers inférieurs à ', n, ' sont : ');
 {Boucle extérieure pour le parcours des valeurs}
 i := 2;
 While (i <= n) Do
 Begin
 
  j := 2;
  diviseur := false;
  
  {Boucle intérieur pour voir est ce que 
   la valeur i est un nombre premier}
  While ((j < i) And not(diviseur)) Do
  Begin
   If (i mod j = 0) Then
    diviseur := true
   Else
    j := j + 1;
  End;
  
  If (not(diviseur)) Then
   WriteLn(i);
  
  {Vérification de la valeur suivante}
  i := i + 1;
 End;
 
End.

L'opérateur "modulo" : un point essentiel pour comprendre la différence entre une définition théorique (mathématique) et une définition pratique (appliquée, informatique)

Enoncé
Ecrire un programme qui lit deux entiers a et b et vérifie est ce que b est un diviseur de a.

Solution
Ma principale motivation pour cette article est une solution que je lis plusieurs fois durant les séances de TD Algorithmique pour les étudiants MI. Les étudiants en Mathématiques et Informatique sont généralement des matheux qui maîtrise les maths et qui projèctent chaque nouvelle notion acquise sur une notion mathématiques.

Dans le cas de vérification si un nombre divise un autre, le code que je lis souvent est le suivant :

Program Diviseur;

Var
 a, b, k : Integer;

Begin
 ReadLn(a, b);
 If (k * b = a) Then
  WriteLn('b divise a')
 Else
  WriteLn('b ne divise pas a');
 
End.

Cette solution n'est même pas "compilable". En effet, la variable k n'a jamais été initialisée. Cela donne des avertissements (Warning) sous des compilateur et des erreur (Error) sous d'autres.

Mais cette solution n'est pas vraiement loin de la réalité. En effet, les étudiants, qui gardent encore un esprit matheux par excellence, reposent sur la définition suivante :

Soit a et b deux entiers.
On dit que b est un diviseur de a s'il existe un entier k tel que k.b = a.

L'erreur n'est pas dans la définition mais dans la traduction de la définition. L'erreur faite par les étudiants ici est plus simple de ce qu'elle parraît. En effet, ils ont montré deux confusions :

1. La déclaration algorithmique est différente de la déclaration mathématique. Décalrer une variable en algorithmique ne veut pas dire qu'elle prendra une valeur sur le champs.
2. L'ordinateur va chercher la bonne valeur pour eux.

Ainsi, une traduction plus correcte de la définition sera de la forme :

Program VerifierDiviseur;

Var
 a, b, k : Integer;
 diviseur : Boolean;

Begin
 ReadLn(a, b);
 k := 2;
 diviseur := false;
 
 While (not(diviseur) And (k < a)) Do
 Begin
  If (k * b = a) Then
   diviseur := true
  Else
   k := k + 1;
 End;
 
 If (diviseur) Then
  WriteLn('b divise a')
 Else
  WriteLn('b ne divise pas a');
 
End.

La suposition "il existe un entier k" nous oblige à le chercher, c'est à dire à parcourir les valeurs des nombres entiers, d'où la boucle.

Alors ce qu'il faut faire, c'est  de choisir la bonne définition. C'est aussi simple que cela. La définition à prendre est la définition la plus élémentaires que nous enseignons aux enfants :

Soient a et b deux entiers.
On dit que b est un diviseur de a si le reste de division de a sur b est nul.

Comment choisir la bonne définition ? Il n'y a pas une méthode exacte; c'est par la pratique, la lecture des codes et l'expérience. Dans ce cas, il fallait lister des opérations possibles et penser à choisir la définition la plus proche d'une telle ou telle opération ou bien celle qui nécessite un code minimal.

Le code sera ainsi :

Program VerifierDiviseur;

Var
 a, b : Integer;

Begin
 ReadLn(a, b);
 
 If (a mod b = 0) Then
  WriteLn('b divise a')
 Else
  WriteLn('b ne divise pas a');
 
End.

Dans les exemples suivants, vous allez voir que cette vérification n'est pas réalisée juste pour faire un affichage. Elle est utilisée pour aider les étudiants à comprendre et utiliser la notion d'une variable booléenne.