Programme pour nombre parfait

Fermé
mounirovic
Messages postés
21
Date d'inscription
dimanche 23 octobre 2005
Statut
Membre
Dernière intervention
17 mars 2009
- 13 janv. 2008 à 19:12
 med - 10 déc. 2012 à 12:52
Bonjour,
je voudrais vous demander une faveur :
j'ai pas su trouver un code pour cette exercice :
Ecrire un programme qui permet de determiner parmi les 100 premiers nombres entiers ceux qui sont parfaits.
Merci
A voir également:

12 réponses

KX
Messages postés
16538
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
21 mai 2022
2 956
20 sept. 2011 à 12:14
Comme tout le monde y va régulièrement de son petit code, je vais y mettre mon grain de sel parce qu'au final tout le monde fait plus ou moins pareil : une boucle de 1 à n/2 (voire de 1 à n) et on calcule à la fin la somme des diviseurs pour comparer avec n.

Pourtant il y a au moins deux méthodes pour faire mieux :

1) si au cours du calcul la somme des diviseurs dépasse déjà n, ce n'est pas la peine de continuer ! Du coup il est intéressant de calculer les plus grand diviseurs en premier.
Exemple avec n=12 dont les diviseurs sont 1, 2, 3, 4 et 6. En commençant par la fin on fait la somme 6+4+3=13, on est déjà supérieur à 12 donc ce n'est pas nécessaire de calculer les diviseurs 2 et 1 pour savoir que 12 n'est pas parfait !

2) si k est un diviseur de n, alors n/k en est également un autre (2 divise 12 donc 6 aussi) donc au lieu d'aller chercher des diviseurs jusqu'à n/2 on peut s'arrêter à sqrt(n).
On parcourt donc uniquement les diviseurs inférieurs à sqrt(n), ce qui fait des calculs avec de "petits" diviseurs, et lorsqu'on a trouvé un diviseur k, on ajoute k ET n/k, ce qui fait qu'on ajoute bien les plus grands diviseurs en premier (k petit --> n/k grand)
Exemple avec n=12, on part de la somme à 1 puisque c'est toujours un diviseur, on fait le calcul avec 2 qui est un diviseur on ajoute donc à la somme 2 ET 6(=12/2), et après on fait le test sur 3 et on rajoute 3 ET 4(=12/3) et on s'arrête d'une part parce que la somme est déjà supérieure à 12 et d'autre part parce que la racine de 12 est 3,46 et qu'on ne va pas au delà (sinon on compterait une deuxième fois le 4 !)
Attention : si k==sqrt(n)==n/k il ne faut bien sûr compter le diviseur qu'une seule fois !

À quoi ça sert d'autant s'embêter ? Par exemple pour savoir si 137438691328 est un nombre parfait, en s'arrêtant à n/2 vous allez faire 69 milliards de calculs n%k alors qu'en vous arrêtant à sqrt(n) vous n'allez en faire "que" 371 millions (ce qui se fait en 1 seconde)
Ces allègements des calculs se feront surtout ressentir si vous cherchez TOUS les nombres parfaits sur un intervalle donné. Par exemple pour chercher les nombres parfaits entre 1 et 100 000, en s'arrêtant à n/2 vous ferez 2.5 milliards de calculs contre 21 millions en s'arrêtant à sqrt(n)...
8
pouvez vous donner le programme écris en c,compiler,prsk j'arrive pas a compiler le programme que j'ai écris, je sais pas ou je fais l'erreur ^^^^
0
KX
Messages postés
16538
Date d'inscription
samedi 31 mai 2008
Statut
Modérateur
Dernière intervention
21 mai 2022
2 956
30 déc. 2011 à 18:50
J'ai déjà posté un code en C mais sur un autre post, regarde Langage C, Nombre parfait
0