Détermination des diviseurs d'un nombre

L'exercice consiste à trouver tous les diviseurs d'un nombre donné. Par exemple, si je dis 20, il faut arriver à trouver que ses diviseurs sont 1, 2, 4, 5, 10 et 20. Bon en fait, 1 et 20 évidemment qu'ils sont diviseurs... N'importe quel nombre est divisible par un et par lui-même. Ce sont surtout 2, 4, 5 et 10 qui sont intéressants. Bon ici, ça va, on peut faire le calcul de tête. Mais s'il s'agit de trouver les diviseurs de 376, c'est moins facile... Comment allons nous procéder ? Par multiplications successives. Par exemple, on cherche les diviseurs de 8 : ce sont 1, 2, 4 et 8. Méthodiquement, on fait :

Pas de chance... Il n'y en a aucun. Bon on continue avec les 4. On va trouver 4X2 = 8, puis avec les 5 il n'y en a aucun, avec les 6 non plus, les 7 non plus, les 8 : Il y en a 1 : 8X1 = 8.

Bon alors comment on met ça en route ? avec une boucle imbriquée, comme ceci

Pseudo-code

AFFICHE "Entre le nombre à analyser"
ACCEPTE Nombre
POUR Ctr = 1 JUSQUA Nombre
  POUR Ctr2 = Ctr JUSQUA Nombre
    SI Ctr * Ctr2 = Nombre
      AFFICHE Ctr " fois " Ctr2 " égale " Nombre
    FIN SI
  SUIVANT Ctr2
SUIVANT Ctr

Améliorations possibles :

1. Optimiser le programme : Il est inutile de faire commencer le compteur à 1
2. Est-il nécessaire de continuer au delà de la moitié ?
3. L'utilisateur doit pouvoir entrer d'autres nombres à analyser

Visual Basic

Message Box successifs

Sub Diviseur()
  Dim QuelNombre As Long
  Dim Ctr As Long
  Dim Ctr2 As Long
  QuelNombre = Val(InputBox("Quel nombre voulez-vous analyser ?"))
  For Ctr = 1 To QuelNombre
    For Ctr2 = 1 To QuelNombre
      If Ctr * Ctr2 = QuelNombre Then
        MsgBox Ctr & " est diviseur de " & QuelNombre
      End If
    Next Ctr2
  Next Ctr
End Sub

Stockage dans un tableau de taille fixe

Sub DiviseurV2()
  Dim QuelNombre As Long
  Dim Ctr As Long
  Dim Ctr2 As Long
  Dim ListeDiviseur(1000)
  Dim Flag As Long

  Flag = 0
  QuelNombre = Val(InputBox("Quel nombre voulez-vous analyser ?"))
  For Ctr = 1 To QuelNombre
    For Ctr2 = 1 To QuelNombre
      If Ctr * Ctr2 = QuelNombre Then
        Flag = Flag + 1
        ListeDiviseur(Flag) = Ctr
      End If
    Next Ctr2
  Next Ctr

  For Ctr = 1 To Flag
    Selection.TypeText ListeDiviseur(Ctr)
    Selection.TypeParagraph
  Next
End Sub

Stockage dans un tableau de taille variable avec ReDim (pour optimiser la place mémoire)
L'utilisation de Preserve évite d'effacer chaque fois le tableau

Sub DiviseurV3()
  Dim QuelNombre As Long
  Dim Ctr As Long
  Dim Ctr2 As Long
  Dim ListeDiviseur()
  Dim Flag As Long

  Flag = 0
  QuelNombre = Val(InputBox("Quel nombre voulez-vous analyser ?"))
  For Ctr = 1 To QuelNombre
    For Ctr2 = 1 To QuelNombre
      If Ctr * Ctr2 = QuelNombre Then
        Flag = Flag + 1
        ReDim Preserve ListeDiviseur(Flag + 1)
        ListeDiviseur(Flag) = Ctr
      End If
    Next Ctr2
  Next Ctr

  For Ctr = 1 To Flag
    Selection.TypeText ListeDiviseur(Ctr)
    Selection.TypeParagraph
  Next
End Sub

Si le nombre n'est divisible que par 1 et par lui même (23 par exemple), il est premier.
Nous allons l'indiquer

Sub DiviseurV4()
  Dim QuelNombre As Long
  Dim Ctr As Long
  Dim Ctr2 As Long
  Dim ListeDiviseur()
  Dim Flag As Long

  Flag = 0
  QuelNombre = Val(InputBox("Quel nombre voulez-vous analyser ?"))
  For Ctr = 1 To QuelNombre
    For Ctr2 = 1 To QuelNombre
      If Ctr * Ctr2 = QuelNombre Then
        Flag = Flag + 1
        ReDim Preserve ListeDiviseur(Flag + 1)
        ListeDiviseur(Flag) = Ctr
      End If
    Next Ctr2
  Next Ctr

  If Flag = 2 Then
    Selection.TypeText QuelNombre & " est un nombre premier que rien ne divise."
    Selection.TypeParagraph
  Else
    For Ctr = 1 To Flag
      Selection.TypeText ListeDiviseur(Ctr)
      Selection.TypeParagraph 
    Next
  End If
End Sub

Optimisation : Utilisation du Modulo (MOD)

Jusqu'ici, nous avons utilisé 2 boucles imbriquées pour voir si un nombre multiplié par un autre donne le résultat recherché. En fait, on gaspille un temps de programmation précieux. Nous avons la possibilité d'utiliser la fonction MOD (Modulo). MOD permet de trouver le reste d'une division. Par exemple 15 MOD 2= 1. Parce que 15/2 = 7, mais il reste 1 (7*2 = 14 + ce fameux 1) = 15. Ca à l'air idiot comme ça, mais dans notre cas, ça va nous rendre de précieux services. Par exemple, si on cherche les diviseurs de 20 :

20 MOD 2 = 0 (20/2=10, reste 0)
20 MOD 3 = 2 (20/3 = 6, reste 2)
20 MOD 4 = 0 (20/4 = 5, reste 0)
A vous maintenant :
20 MOD 5 = 0 (20/5 = 4, reste ?)
20 MOD 6 = 2 (20/6 = ?, reste ?)
20 MOD 7 = ? (20/7 = ?, reste ?)
20 MOD 8 = ? (?/? =?, reste ?)
20 MOD 9 = ?
20 MOD 10 = ?

ça ne sert à rien d'aller plus loin que la moitié. On se doute bien que 20 n'est pas divisible par 11,12,13,14,15,16,17,18 ni 19. En fait, avec ce MOD, on constate simplement que lorsque le modulo = 0, 20 est divisible par ce nombre (2, 4, 5 et 10). Voici une version largement plus rapide du programme de recherche des diviseurs :

Sub DiviseurOptimise()
  Dim QuelNombre As Long
  Dim Ctr As Long
  QuelNombre = Val(InputBox("Quel nombre voulez-vous analyser ?"))
  ' Nous partons de 2, parce que ça ne sert a rien de tester 1,
  ' et on va jusqu'à la moitié du nombre, car on sait qu'il n'y a plus aucun diviseur après.
  For Ctr = 2 To QuelNombre / 2
    If QuelNombre Mod Ctr = 0 Then
      MsgBox Ctr & " est diviseur de " & QuelNombre
    End If
  Next Ctr
End Sub