Discussion :

[pierre1976]

Bonjour!
Quelqu'un pourrait m'aider a résoudre cette exercice s'il vous plait?

Un nombre parfait est un entier positif supérieur à 1, égal à la somme de ses
diviseurs ; on ne compte pas comme diviseur le nombre lui-même.
Exemple :
6 est un nombre parfait puisque : 6 = 3 + 2 + 1.
Écrire un algorithme qui qui nous dit si un entier N saisi par l’utilisateur est parfait ou non.

[anapurna]

salut

si j ai tout compris de vérifier si un nombre que tu entre au clavier est un nombre parfait
l’algorithme est assez simple


il te suffit de faire une boucle de 2 a Ton chiffre divisé par 2
dans cette boucle tu vérifie si le diviseur est un nombre entier
si oui tu incrémente la somme du diviseur

a la fin de la boucle tu vérifie que le nombre entre en paramètre est égale à la somme + 1
si oui c'est un nombre parfait sinon ce ne l'est pas

[Flodelarab]

Bonjour

Il faut faire une décomposition en facteurs premiers.
On sait qu'il suffit de tester jusqu'à la racine du nombre pour les trouver. (Et non pas la moitié ...)

Si on se place dans le cas général, ton problème n'a pas de solution puisqu'on ne sait pas factoriser un nombre quelconque.

Une méthode peut être de garder sous le coude une liste des nombres premiers jusqu'à 1 million en espérant que l'utilisateur n'aille pas au-delà de mille millards.

[anapurna]

salut

pas besoin d'aller au delà de la moitie du nombre puisque ce ne seras forcement plus un nombre parfait

le nombre parfait ne peut se diviser que par soi même et ne voulant que des diviseur entier la valeur de ton diviseur ne peut absolument pas être supérieur à sa moitié

quelque soit le chiffre si tu divise ton nombre par un nombre supérieur a sa moitié ton diviseur ne pourra être compris qu'entre 1.000000001 et 1.999999999


prenons 28
28 div 2 = 14
donc je boucle de 2 a 14
28 mod 2 = 0
Somme = 2
28 mod 3 <> 0
28 mod 4 = 0
Somme = 2+4 = 6
28 mod 5 <> 0
28 mod 6 <> 0
28 mod 7 <> 0
Somme = 6+7 = 13;
28 mod 9 <> 0
...
28 mod 14 = 0
Somme = 13 +14 = 27

somme = 27+1 = 28 ... nombre parfait

[Flodelarab]

Pardon d'insister mais la racine est inférieure à la moitié. Tu veux explorer jusqu'à 14 alors qu'explorer jusqu'à 5 est suffisant.

28=2*14=2*2*7=2²*7

Les diviseurs sont donc 1 2 4 7 14 28.

[Prof]

Bonjour.

Il est totalement inutile de chercher les facteurs premiers de N pour savoir si N est parfait.

Lorsqu'on cherche à savoir si un entier N est premier, une méthode consiste à tester tous les entiers k compris entre 2 et racine(N) et examiner si k divise N.
Si aucun de ces entiers k ne divise N, alors on peut conclure que N est premier.

Ce n'est pas du tout ce qu"il faut faire ici !

Pour savoir si N est parfait, il faut chercher tous les diviseurs de N autres que N, faire la somme de ces diviseurs et comparer le résultat avec N.
D'où l'algorithme suivant, écrit en pseudo-langage :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
n:ENTIER
k:ENTIER
reste:ENTIER
somme:ENTIER
 
ENTRER n
somme <- 0
POUR k DE 1 A (n DIV 2) FAIRE
     reste <- (n MODULO k)
     SI reste = 0
        ALORS somme <- somme + k
     FINSI
FINFAIRE
SI somme = n
   ALORS AFFICHER(" n est parfait ")
   SINON AFFICHER(" n n'est pas parfait ")
FINSI

Je suppose que l'on dispose de la division entière : DIV retourne le quotient et MODULO le reste.

[Flodelarab]

Et ça ne te choque pas de préconiser 14 étapes quand 5 sont nécessaires ?

[Prof]

Et ça ne te choque pas de préconiser 14 étapes quand 5 sont nécessaires ?

Comme je l'ai bien indiqué par ma réponse précédente, on cherche à savoir si N est parfait, on ne cherche pas à savoir si N est premier.

La limite de racine(N) intervient dans l'étude de la primalité de N, mais pas quand on cherche à savoir si N est parfait.

Exemple avec 28 :
La partie entière de racine(28) est 5.
Si on étudie les diviseurs de 28 entre 1 et 5, on trouve : 1,2,4.
Et maintenant, on fait quoi ?
Comment, à partir de 1,2,4, trouve-t-on la liste complète des diviseurs de 28 : 1,2,4,7,14,28 ?

Il y a peut-être un algorithme qui fait çà, mais alors c'est du genre " pourquoi faire simple quand on peut faire compliqué " ...

Je pense que l'auteur du post initial souhaitait une réponse simple à sa question.
J'ai donc donné un algorithme simple à comprendre, et qui fonctionne parfaitement.

[Flodelarab]

Non, on ne trouve pas 1, 2, 4. Comme je te l'ai montré, on trouve 2, 2 et 7.
La liste complète des diviseurs tombent tous cuits.
Et la perfection du nombre aussi.

Si je te demande si 137 438 691 328 est parfait, tu vas faire 70 milliards d'opérations ? Bon, ben, à demain!

[Prof]

Non, on ne trouve pas 1, 2, 4. Comme je te l'ai montré, on trouve 2, 2 et 7.
La liste complète des diviseurs tombent tous cuits.

Tu n'as rien montré tant que tu n'as pas donné un algorithme précis.

Personnellement, j'ai donné un algorithme qui fonctionne.
Alors, fais de même et donne un algorithme en entier.

On pourra alors comparer les deux solutions et voir laquelle est la plus efficace.

[tbc92]

Inutile d'aller jusqu'à n/2 ; racine(n) suffit.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
Pour tout entier i entre 1 et racine(n)
    si n est un multiple de i alors 
         somme += i 
         si i <> n/i alors somme += n/i
    fin si 
fin pour
si somme = n alors afficher ( "n est parfait")

[Flodelarab]

Tu veux qu'on te montre, on va te montrer:

Code bash :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
$ N=137438691328; factor "$N"|sed 's/.*: //;s/ /\n/g'|awk 'BEGIN{a[1]++;} {for (i in a) a[i*$1]++;} END{for (i in a) print i;}'|awk '!/'"$N"'/{somme += $1} END{print somme;print '"$N"'}'          
137438691328
137438691328
$ N=28; factor "$N"|sed 's/.*: //;s/ /\n/g'|awk 'BEGIN{a[1]++;} {for (i in a) a[i*$1]++;} END{for (i in a) print i;}'|awk '!/'"$N"'/{somme += $1} END{print somme;print '"$N"'}'                    
28
28
$ N=16; factor "$N"|sed 's/.*: //;s/ /\n/g'|awk 'BEGIN{a[1]++;} {for (i in a) a[i*$1]++;} END{for (i in a) print i;}'|awk '!/'"$N"'/{somme += $1} END{print somme;print '"$N"'}'                    
15
16
$ N=24; factor "$N"|sed 's/.*: //;s/ /\n/g'|awk 'BEGIN{a[1]++;} {for (i in a) a[i*$1]++;} END{for (i in a) print i;}'|awk '!/'"$N"'/{somme += $1} END{print somme;print '"$N"'}'
36
24

137438691328 est un nombre parfait.
28 est un nombre parfait.
16 n'est pas un nombre parfait. (Il est déficient)
24 n'est pas un nombre parfait. (Il est abondant)

[Prof]

Pour tbc92 : cette fois, je suis d'accord.

1) Cet algorithme est entièrement détaillé.

2) Il ne cherche les diviseurs que jusqu'à racine(n).
Il est donc plus rapide que celui que j'avais proposé.

Un tout petit détail : pour i=1 on ajoute n à la somme ; le test final doit donc comparer somme et 2*n.

A part cela, cet algorithme est vraiment élégant !

Pour Florelarab : la question initiale demandait un algorithme, ce qui sous-entend des instructions et des opérations élémentaires.

L'utilisation de primitives de haut niveau, comme factor, n'est pas autorisée dans ce type d'exercice.

La méthode consistant à chercher les facteurs premiers de n n'est pas bonne puisque la décomposition d'un nombre en facteurs premiers est un problème NP pour lequel on ne connait pas de solution polynomiale ( ce qui assure pour l'instant la sécurité du cryptage RSA ).

Par contre, les deux algorithmes ci-dessus sont polynomiaux : O(n) pour celui que j'ai donné, O(racine(n)) pour celui de tbc92.

[Flodelarab]

C'est pas possible de voir une mauvaise foi pareille.

Si tu étais un peu moins obtus, tu aurais vu que mon premier message de cette discussion a tout de suite dit que le problème était insoluble dans le cas général. Justement parce que la factorisation d'un nombre quelconque n'est pas possible.

La solution de tbc92 et la mienne sont exactement la même, d'un point de vu algorithmique. Et si tu ne peux pas trouver de facteur de ton nombre, tu ne pourras jamais déterminer s'il est parfait (hors propriété spécifique).

La méthode consistant à chercher les facteurs premiers de n n'est pas bonne puisque la décomposition d'un nombre en facteurs premiers est un problème NP pour lequel on ne connait pas de solution polynomiale ( ce qui assure pour l'instant la sécurité du cryptage RSA ).

Ne fais pas celui qui comprend car manifestement, si tu ne comprends pas qu'il faut factoriser pour réussir cet exercice, tu n'as rien compris. La route est longue avant de pouvoir se dire "prof".

[anapurna]

salut

bien vu pour la racine carré même si ce n'est qu'une amélioration et ou optimisation de mon algorithme
je m'explique :
effectivement mon algo test tout les solutions possible jusqu’à la moitié
le tiens en revanche diminue significativement le nombre car à chaque boucle tu trouve les deux élément constitutif de la multiplication
sauf qu'il ne faut pas commencer à 1 sinon ton algo est faux
car pour 1 le pendant vaut la valeur a atteindre ce qui te fera dépasser la somme de tes éléments

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
  somme := 0;
  POUR TOUT i  entre 2 et  RACINE(n) FAIRE
  DEBUT POUR
    SI  n mod i = 0 ALORS
    DEBUT SI
      somme = somme + i;
      SI i <> (n div i)  ALORS
        somme = somme + (n div i);
    FIN SI
  FIN POUR
  somme = somme +1;
  SI somme =  n  ALORS
     afficher ('n est parfait');

[garnier54]

bonjour,

j'ai essayé de mettre algorithme en c# mais il ne marche pas
9 pas ex retourne 4 alors que c'est un carre parfait
merci de votre aide.

Code C# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private ulong carreparfaitxx(ulong N)
        {
            ulong compteur;
            ulong somme = 0;
            double racine = Math.Sqrt(N);
         for (compteur = 2; compteur <= racine; compteur++)
         {
                double xx = N % compteur;
 
                if (xx == 0)
             {
                    somme =  somme + compteur;
 
                    if (compteur != (N / compteur))
                        {
                            somme = somme + (N / compteur);
                        }
                    }
            }
 
    somme = somme +1;
 
  if (somme == N)
     {
    return N;
     }
    else
 
     {
    return 0;
     }
 
    }

[tbc92]

La discussion parlait de nombre parfait. Les plus petits nombres parfaits sont 6, 28, 496 , 8128... Regarde la page Wikipedia sur les nombres parfaits si tu veux.
Toi tu parles de carré parfait.
Totalement différent.

[wiwaxia]

Bonjour,

Le programme suivant détecte tous les nombres parfaits entre 2 et 40 millions.

L'iessentiel c'est évidemment le bloc d'instructions présent dans la procédure centrale Calc_Sdiv(VAR k_: Word; N_: Z_32) où se calcule la somme des diviseurs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 PROGRAM N_Parfait;     // 6  28  496  8128  33550336  8589869056
 
 USES Crt, E_Texte;
 
 PROCEDURE Aff_NP(k: Word; Np: LongInt);
   VAR y: Byte;
   BEGIN
     y:= 2;   Inc(y, k);
     E(0015); Wt(5, y, 'Rang: k = ');                    // Affichage d'un texte Wt(x, y, '******')
     E(0009); Write(k:5);
     E(0015); Write('   Nombre parfait: Np = ');
     E(0010); Write(Np:+10); E(0012)
   END;
 
 PROCEDURE Calc_Sdiv(VAR k_: Word; N_: Z_32);
   VAR K1: Word; d, q, r, s: LongInt;
   BEGIN
     d:= 1; s:= 1; K1:= k_;
     REPEAT
       Inc(d); q:= N_ DIV d; r:= N_ MOD d;
       IF (r=0) THEN
         IF (d<q) THEN Inc(s, d + q)
                  ELSE IF (d=q) THEN Inc(s, d)
     UNTIL (d>q);
     IF (s=N_) THEN BEGIN
                      k_:= K1 + 1; Aff_NP(k_, N_)
                    END
   END;
 
 PROCEDURE Enumeration;
   CONST N1 = 2; N2 = 40000000;
   VAR k: Word; Nombre: LongInt;
   BEGIN
     E(1012);                    // Couleurs du texte, du fond / effacement de l'écran
     FOR Nombre:= N1 TO N2 DO BEGIN
                                IF ((Nombre MOD 1000)=0) THEN
                                  We(60, 3, Nombre, 10);                    // Affichage d'un entier We(x, y, N, format)
                                Calc_Sdiv(k, Nombre)
                              END;
     We(60, 3, Nombre, 10); A_
   END;
 
 BEGIN
   Enumeration
 END.

... j'ai essayé de mettre algorithme en c# mais il ne marche pas
9 pas ex retourne 4 alors que c'est un carre parfait ...

C'est en soi normal, puisque pour N = 9 , la somme des diviseurs vaut 4: S = 1 + 3 .
Sa qualité de carré parfait intervient au niveau de l'incrémentation de la somme (ligne 23):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
         IF (d<q) THEN Inc(s, d + q)
                  ELSE IF (d=q) THEN Inc(s, d)