Déterminer l'ensemble des diviseurs d'un entier
Comment déterminer l'ensemble des diviseurs d'un nombre entier n ?
Pour chaque entier inférieur à n :
- Tester si n est un multiple de cet entier (par division euclidienne de n)
- Si oui, cet entier et le quotient de la division sont des diviseurs de n
- Si non, cet entier n'est pas un diviseur de n
Remarques :
- Il n'est pas utile de faire la recherche au-delà de la racine carrée de n, car tous les divisieurs sont déjà trouvés.
- Il est souvent possible de gagner du temps dans la recherche en évitant d'effectuer toutes les divisions euclidiennes : penser à utiliser les critères de divisibilité d'un entier.
- Il est souvent possible de gagner encore du temps dans la recherche, par exemple :
- Si n n'est pas divisible par 2, alors il n'est divisible par aucun nombre pair
- Si n est divisible par 3 et par 5, alors il est aussi divisible par 3 x 5 = 15
- Lorsque n est un carré parfait, sa racine carrée est un diviseur de n, qu'il est inutile d'écrire deux fois dans la liste des diviseurs.