Listes des nombres parfaits inferieures à n

Soyez le premier à donner votre avis sur cette source.

Vue 15 282 fois - Téléchargée 1 004 fois

Description

Un nombre parfait est un nombre qui est egale a la somme de ses diviseurs. Ce programme permet d'afficher tous les nombres parfaits inferieurs à un nombre N

Source / Exemple :


#include<stdio.h>
#include<conio.h>
void main()
{
int x,i,j,r,som=0;

do{
	printf("Entrer votre nombre ");
	scanf("%i",&x);

  }while(x<0);// controle du nombre saisi par l'utilisateur

 for(j=1;j<x;j++)//parcourt de tous les nombres jusqu'a x
  {
    som=0;
 	 for(i=1;i<j;i++)
  	{
  	r=j%i;

  		if(r==0)
  		{
      	som=som+i;
     	}
    }
  		if(j==som)
  		{
  		printf("\n%d est parfait ",j);
  		}
  			else
  			{
  		  //	printf("\n%d n'est pas parfait ",j);

   		}
  }

getch();
}

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

dubstructor
Messages postés
15
Date d'inscription
vendredi 24 juillet 2009
Statut
Membre
Dernière intervention
24 février 2010

Bonsoir ,

// 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 ;
}
pgl10
Messages postés
312
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
5 février 2020
1
Ce code est parfait pour retrouver les 4 premiers nombres
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.
cs_Trezeguet
Messages postés
3
Date d'inscription
mardi 5 février 2008
Statut
Membre
Dernière intervention
14 février 2012

Bjr j'aimerais apprendre à programmer en VB office svp aidez moi a trouver la documentation
cs_Trezeguet
Messages postés
3
Date d'inscription
mardi 5 février 2008
Statut
Membre
Dernière intervention
14 février 2012

Merci pour le commentaire rclsilver
rclsilver02
Messages postés
132
Date d'inscription
mercredi 19 mars 2003
Statut
Membre
Dernière intervention
10 février 2012

Salut,

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.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.