Programme pour nombre parfait
mounirovic
Messages postés
21
Date d'inscription
Statut
Membre
Dernière intervention
-
med -
med -
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
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:
- Nombre parfait en python
- Citizen code python avis - Accueil - Outils
- Nombre de jours entre deux dates excel - Guide
- Nombre facile - Télécharger - Outils professionnels
- Notes un diner presque parfait a imprimer - Forum Cinéma / Télé
- Ascii nombre de caractères - Guide
12 réponses
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)...
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)...
marie
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 ^^^^
KX
Messages postés
16761
Date d'inscription
Statut
Modérateur
Dernière intervention
3 020
J'ai déjà posté un code en C mais sur un autre post, regarde Langage C, Nombre parfait
