LISTES DES NOMBRES PARFAITS INFERIEURES À N
rclsilver02
Messages postés
130
Date d'inscription
mercredi 19 mars 2003
Statut
Membre
Dernière intervention
10 février 2012
-
30 oct. 2009 à 13:12
dubstructor Messages postés 15 Date d'inscription vendredi 24 juillet 2009 Statut Membre Dernière intervention 24 février 2010 - 22 janv. 2010 à 05:30
dubstructor Messages postés 15 Date d'inscription vendredi 24 juillet 2009 Statut Membre Dernière intervention 24 février 2010 - 22 janv. 2010 à 05:30
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/50766-listes-des-nombres-parfaits-inferieures-a-n
https://codes-sources.commentcamarche.net/source/50766-listes-des-nombres-parfaits-inferieures-a-n
22 janv. 2010 à 05:30
// tous les nbs parfaits connus sont pairs.
Pas faux, mais il n'est pas prouvé qu'un nombre parfait ne puisse pas être impair.
Sinon l'implé de PGL10 est propre, en tout cas plus que celle de Trezeguet qui n'a pas vu qu'il suffisait d'aller jusqu'à la racine du nombre testé, en sachant que pour tout diviseur d trouvé, on peut directement ajouter un autre diviseur d' = n/d .
De plus si la somme dépasse notre nombre, inutile de poursuivre !
if(somme>nb) break;
Accessoirement pour Trezeguet qui nous demandait des conseils d'optimisation :
# r=j%i;
#
# if(r==0)
ce genre de complication ne sert à rien si on ne se sert pas de j%i par la suite (auquel cas, il serait plus utile de le stocker ; mais ici on peut faire l'économie d'une affectation, directement suivie d'une extraction, à chaque itération).
Enfin, on a quelques résultats intéressants sur les nombres parfaits PAIRS (qui n'exclut en aucun cas l'existence possible de parfaits impairs, seulement ça n'apprend rien sur eux) :
soit p un entier tel que 2^p-1 soit premier (2^p-1 est alors appelé le p-ième nombre de Mersenne, noté Mp), alors [2^(p-1)]*[2^p-1] est parfait - évidemment pair -, et réciproquement (ie, TOUS les nombres parfaits pairs s'écrivent [2^(p-1)]*[2^p-1] avec p un entier tel que 2^p-1 est premier).
Un tel nombre p est nécessairement premier (mais ça ne suffit pas : par exemple 2^11-1=89*23).
Pour savoir si 2^p-1 est premier, il faut donc déjà obligatoirement avoir p premier, et un autre résultat dit que les diviseurs potentiels de 2^p-1 sont à chercher parmi les nombres de la forme 2*k*p+1. On peut donc avancer dans les tests par sauts de 2p.
On peut aussi utiliser l'algorithme suivant (test de Lucas-Lehmer) :
2^p-1 est-il premier ?
Si p n'est pas premier : non.
Si p est premier : construire la suite définie par S(1)=4 et S(n+1)=S(n)^2-2 jusqu'à obtenir S(p-1) ; tester alors si S(p-1) est divisible par 2^p-1. Oui : 2^p-1 est premier ; non : il ne l'est pas.
(attention à ne pas appliquer l'algorithme tel quel, les calculs seraient énormes ! il faut calculer modulo 2^p-1).
Voilà avec tout ça on peut arriver à faire quelque chose ; si par exemple on veut savoir si un nombre donné est parfait :
- si il est impair, on n'a aujourd'hui pas d'autre solution que l'algorithme "naïf" ;
- si il est pair : est-il de la forme 2^(p-1)*(2^p-1), c'est-à-dire s'écrit-il en binaire :
1111.....1111000......00000
où, en numérotant à partir de 0 (LSB), on n'a que des "1" de la position p-1 à 2p-2 ?
- si oui : le nombre p ainsi obtenu est-il premier ?
- si oui : tester si 2^p-1 = 11111...11111 (avec p "1" binaires) est
premier.
- dans tous les autres cas, il n'est pas parfait.
Si on veut énumérer les nombres parfaits PAIRS, la méthode est un peu différente :
- énumérer les nombres premiers p.
- pour chaque p, tester si 2^p-1 est premier.
- si oui : (2^p-1)*(2^(p-1)) est le n-ème nombre parfait pair.
Dans le cas de la première méthode, on pourrait donc avoir l'implémentation suivante, en supposant un type d'entiers de taille illimité que j'appelle huge_int, avec les opérations usuelles définies pour ce type :
int main()
{
huge_int nombre ;
do {
cout << "Nombre pair à tester ? " << endl ;
cin >> nombre ; //seul mode de saisie envisageable, avec surcharge correcte de >>
} while(nombre<=0 || nombre&1) ;
huge_int temp=nombre ;
long int p=-1; //sert à compter les bits de "nombre", donc un long int devrait //suffire, un nombre même de taille non limitée par son type ne peut dépasser l'espace mémoire
int flag=0 ;
do {
flag += temp&1 ;
temp >>= 1 ;
p++ ;
} while (!flag) ; //à ce niveau p donne la position du premier 1 rencontré,
//et "temp" se termine par un 1.
//on cherche alors à déterminer si "temp" n'est composé que de uns.
//on peut vérifier que dans ce cas, en faisant la somme bit à bit avec
//son augmenté de un, on obtient 0 : par exemple,
// 1111 & 10000 = 0, alors que c'est faux pour les autres nombres.
if(temp&(temp+1) || isPrime(p+1)) {
cout << "\nNombre non parfait !\n" ;
getch() ;
return 0 ;
} //isPrime est un test de primalité quelconque : méthode naïve (crible), probabiliste
//(type Fermat) etc ..., non développé ici
long int q=-1 ;
huge_int temp2=temp+1 ; //la valeur que temp a ici servira plus bas
while(1)
{
if(!(temp2&1)) {
q++ ; temp2 >>= 1 ;
} else break ;
} //q est le nombre de 1 restants, diminué de 1.
if(p!=q) {
cout << "\nNombre non parfait !\n" ;
getch() ;
return 0 ;
}
//ici on est sûr que le nombre a la bonne forme.
//il s'agit donc maintenant de tester la primalité de 1111...11111 = temp .
//la méthode est développée puisqu'il existe des tests spécifiques à ce type de nombre:
//test de Lucas-Lehmer.
p++ ;
huge_int s=4 ;
long int i ;
for(i=2;i<=p-1;i++)
s=(((s%temp)*(s%temp))-2)%temp ;
if(s==0) //pas besoin de refaire un modulo pour tester la divisibilité par temp
cout << "\nCe nombre est parfait !" ;
else cout << "\nNombre non parfait ." ;
getch() ;
return 0 ;
}
31 oct. 2009 à 15:42
parfaits qui étaient déjà connus à l'époque des grecs
anciens ( Euclide ... ). Mais il est illusoire de calculer
le 5-ième avec un code comme celui-ci. Par contre en reprenant
http://www.cppfrance.com/code.aspx?ID=25648 comme suit :
#include <stdio.h>
#include <stdlib.h>
#define nmax 34000000
int main(){ // tous les nbs parfaits connus sont pairs.
long int nb, somme, div, quot;
for(nb=2; nb<=nmax; nb=nb+2){
somme=1;
for(div=2; div*div<=nb; div++){
if(nb%div==0){
quot=nb/div;
if (div==quot) somme=somme+div;
else somme=somme+div+quot;
}
if(somme>nb) break;
}
if (nb==somme)
printf("\n -> nombre parfait : %d", nb);
}
printf("\n\n");
system("pause");
return 0;
}
on peut trouver le 5-ième avec une poignée de minutes d'attente. Ce qui est mieux.
30 oct. 2009 à 19:50
30 oct. 2009 à 19:46
30 oct. 2009 à 13:12
Je pense que tu aurais pu, dans ta description, faire un rappel pour expliquer ce qu'est un nombre parfait, peut-être aussi expliquer comment ton code fonctionne etc... Eventuellement donner quelques exemples d'une utilisation concrète (à quoi ça pourrait servir).
Bonne continuation en tous cas :)
Cordialement,
rclsilver.