Nombres parfaits — exercice corrigé de programmation Java (école d'ingénieur) (chapitre 3)

Nombres parfaits

Instructions de contrôle · niveau 3 (difficile)

Énoncé

Un entier est parfait s'il est égal à la somme de ses diviseurs autres que lui-même ( $6 = 1 + 2 + 3$ ). Afficher les nombres parfaits jusqu'à $10000$ . Pour aller vite, on ne cherchera les diviseurs que jusqu'à $n$ , en ajoutant à chaque diviseur $d$ trouvé son associé $n / d$ .

Corrigé


public class Parfaits {
    public static void main(String[] args) {
        for (int n = 2; n <= 10000; n++) {
            int somme = 1;                      // 1 divise tout n >= 2
            for (int d = 2; d * d <= n; d++) {
                if (n % d == 0) {
                    somme += d;
                    if (d != n / d) {
                        somme += n / d;          // le diviseur associé
                    }
                }
            }
            if (somme == n) {
                System.out.print(n + " ");
            }
        }
        System.out.println();
    }
}


6 28 496 8128

Les diviseurs vont par paires $(d, n / d)$ avec $d \leq n$ ; quand $d = n / d$ (si $n$ est un carré), il ne faut le compter qu'une fois. On part de $1$ et non de $1 + n$ , puisque $n$ lui-même n'est pas compté. La boucle intérieure fait environ $n$ tours au lieu de $n$ : pour $n = 10000$ , $100$ au lieu de $10000$ .