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

12 réponses

KX Messages postés 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
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 16753 Date d'inscription samedi 31 mai 2008 Statut Modérateur Dernière intervention 25 novembre 2024 3 019
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