Perfect Number Program In Python : Comment vérifier si un nombre est parfait ou non ?
Publié: 2021-01-29introduction
Un nombre est dit être le nombre parfait si la somme de ses propres diviseurs (sans compter le nombre lui-même) est égale au nombre.
Pour avoir une meilleure idée, considérons un exemple, les diviseurs propres de 6 sont 1, 2, 3. Maintenant, la somme de ces diviseurs est égale à 6 (1+2+3=6), donc 6 est dit être un nombre parfait . Alors que si nous considérons un autre nombre comme 12, les diviseurs propres de 12 sont 1, 2, 3, 4, 6. Or la somme de ces diviseurs n'est pas égale à 12, donc 12 n'est pas un nombre parfait.
La programmation en Python est relativement plus simple et plus amusante par rapport à d'autres langages en raison de sa syntaxe plus simple et de sa bonne lisibilité. Maintenant que nous avons compris le concept de nombre parfait, écrivons un programme python pour vérifier si un nombre est un nombre parfait ou non. Construisons un code python pour vérifier si l'entrée utilisateur donnée est un nombre parfait ou non et explorons le plaisir de coder avec python. Jetez un œil à nos programmes de science des données si vous souhaitez acquérir une expertise.
Lire : Programmes de modèles Python
Table des matières
Programme Python
Une solution de base pour trouver un nombre parfait consiste à boucler sur 2 jusqu'au nombre-1, à maintenir la somme de ses propres diviseurs et à vérifier si la somme est égale au nombre.
| n=int(input("entrez le nombre")) somme=1 pour i dans la plage (2, n): si(n%i==0): somme=somme+i si(somme==n): print(n,"est un nombre parfait") autre: print(n,"n'est pas un nombre parfait") |
Parcourons le code.
Nous initialisons d'abord n avec l'entrée utilisateur et le transtypons en entier car par défaut l'entrée utilisateur est lue comme une chaîne en python. Il faut vérifier si n est un nombre parfait ou non. Notez que nous initialisons la somme avec 1 car 1 est un diviseur propre pour tous les entiers (à l'exception de zéro), de sorte que nous pouvons exclure une itération dans la boucle et commencer directement à partir de 2.
Nous bouclons de 2 au nombre-1 et ajoutons les nombres entiers à la somme s'il s'agit d'un diviseur approprié. Et enfin, lorsque nous sortons de la boucle, nous vérifions si la somme obtenue est égale au nombre ou non. Un morceau de gâteau, n'est-ce pas ?
Version peu optimisée
Après avoir testé le programme ci-dessus, nous pouvons nous demander si nous pouvons l'optimiser ? Eh bien, mais nous pouvons réduire le nombre d'itérations à nombre/2 sans changer l'algorithme. Parce que nous avons eu l'idée qu'un nombre ne peut pas avoir de diviseur propre supérieur à nombre/2.
| n=int(input("entrez le nombre")) somme=1 pour i dans la plage (2,n//2+1) : si(n%i==0): somme=somme+i si(somme==n): print(n,"est un nombre parfait") autre: print(n, "n'est pas un nombre parfait") |
L'extrait ci-dessus est presque similaire au précédent, avec la seule différence de boucler jusqu'au numéro/2. Notez que nous effectuons une division entière pour éviter de le convertir en un type flottant, et nous bouclons jusqu'à n//2+1 car le dernier entier de la plage n'est pas pris en compte dans la boucle python.
Limites
Lorsqu'on nous demande de trouver des nombres parfaits dans une plage donnée, notre solution consommerait du temps proportionnel au nombre ^ 2, c'est-à-dire une complexité temporelle O (n²). Parce que nous devons parcourir chaque nombre dans la plage donnée, puis vérifier les diviseurs appropriés pour chaque nombre. Et peu de nombres satisfont la condition du nombre parfait. Par exemple, le nombre de nombres parfaits compris entre 0 et 1 000 n'est que de 3 (6, 28, 496).
Il existe une solution optimisée pour cela où nous n'avons pas besoin de boucler sur tous les éléments pour trouver les diviseurs appropriés, la formule d'Euclide indique que 2 n −1 (2 n − 1) est un nombre parfait pair où à la fois n, (2 n − 1) est nombres premiers. Par exemple, 6 satisfait l'équation ci-dessus avec n comme 2 et les deux 2, 2 2 − 1 (2 2 − 1 = 3) sont des nombres premiers. Mais nous ne pouvons pas répondre si on nous demande de trouver s'il existe des nombres parfaits impairs.
De plus, nous savons que chaque langage a une limite à la plage d'entiers qu'il peut stocker. Avec cette limitation, nous n'aurons peut-être pas le moyen de trouver le plus grand nombre parfait.
Toutes ces limitations sont rencontrées si notre nombre d'entrées est grand, mais si notre nombre d'entrées est petit, notre solution initiale fonctionnera en moins de temps.
Lire aussi : Framework Python pour le développement Web
Conclusion
Nous connaissons la définition et comprenons le concept derrière le nombre parfait. Marche à travers une solution de base pour trouver un nombre est un nombre parfait ou non. Et après avoir regardé la solution initiale, nous l'avons un peu optimisée en réduisant le nombre d'itérations. Nous avons traversé les limites de notre algorithme et discuté de la formule d'Euclide pour trouver le nombre parfait pair.
Maintenant que vous connaissez le programme python pour vérifier si un nombre est un nombre parfait ou non. Essayez d'écrire le code par vous-même et essayez de l'optimiser si vous trouvez des itérations qui se chevauchent. Essayez également de construire le code pour trouver des nombres parfaits dans la plage de nombres donnée.
Si vous êtes curieux d'en savoir plus sur Python, la science des données, consultez le programme Executive PG en science des données de IIIT-B & upGrad qui est créé pour les professionnels en activité et propose plus de 10 études de cas et projets, des ateliers pratiques, du mentorat avec des experts de l'industrie. , 1-on-1 avec des mentors de l'industrie, plus de 400 heures d'apprentissage et d'aide à l'emploi avec les meilleures entreprises.
Expliquez les complexités du programme de nombres parfaits en Python.
Un nombre est dit parfait s'il est égal à la somme de ses diviseurs. Pour vérifier si un nombre est parfait ou non, nous avons deux approches. La première approche est une approche naïve où la complexité temporelle est O(n2) puisque nous itérons "j" fois pour chaque "i" et vérifions ses diviseurs.
La deuxième approche est la solution optimisée où la complexité temporelle est O(√n). Ici, nous n'avons pas besoin d'itérer sur chaque nombre. On peut directement le conclure en utilisant la formule d'Euclide qui est :
2n−1(2n − 1), où n et 2n sont des nombres premiers.
Cependant, cette formule ne fonctionne pas pour les nombres parfaits impairs et nous devons donc leur trouver une autre approche.
Quelles sont les limites des approches du Perfect Number Program ?
Ces deux approches sont bonnes, mais seulement dans une certaine mesure. Aucun d'entre eux ne peut être considéré comme l'approche parfaite en raison de certains détails techniques. Les limites de ces approches sont les suivantes :
1. La première approche naïve est pire car elle consomme beaucoup de temps et de mémoire et a une complexité temporelle de O(n2). En effet, nous utilisons une boucle imbriquée et itérons la boucle interne n fois pour chaque élément de la boucle externe. Cette approche est naïve et donnera TLE pour des valeurs plus grandes de n et n'est donc pas recommandée.
2. On a alors une approche optimisée qui résout le problème en O(√n). C'est une bonne approche à moins que les nombres parfaits impairs n'entrent en jeu. Nous ne pouvons pas vérifier les nombres parfaits impairs avec cette approche car elle est basée sur la "formule d'Euclide pour les nombres parfaits pairs" qui ne fonctionne que pour les nombres parfaits pairs.
Python est-il adapté à la programmation compétitive ?
Python a évolué à partir de C/C++ et même de Java et est considéré comme le langage le mieux adapté à des fins de recherche et de développement. Mais lorsqu'il s'agit de programmation compétitive, la majorité de la communauté de programmation évite Python. La raison étant que Python est le plus lent parmi ces trois langages.