Programul Număr Perfect în Python: Cum să verificați dacă un număr este perfect sau nu?
Publicat: 2021-01-29Introducere
Se spune că un număr este numărul perfect dacă suma divizorilor săi proprii (fără a include numărul în sine) este egală cu numărul.
Pentru a ne face o idee mai bună, să luăm în considerare un exemplu, divizorii proprii ai lui 6 sunt 1, 2, 3. Acum, suma acestor divizori este egală cu 6 (1+2+3=6), deci se spune că 6 este un număr perfect . În timp ce dacă luăm în considerare un alt număr ca 12, divizorii proprii ai lui 12 sunt 1, 2, 3, 4, 6. Acum suma acestor divizori nu este egală cu 12, deci 12 nu este un număr perfect.
Programarea în Python este relativ mai simplă și mai distractivă în comparație cu alte limbi, datorită sintaxei sale mai simple, a lizibilității bune. Acum că suntem clari cu conceptul de număr perfect, să scriem un program python pentru a verifica dacă un număr este un număr perfect sau nu. Să construim un cod python pentru a verifica dacă introducerea dată de utilizator este un număr perfect sau nu și să explorăm distracția în codificare cu python. Aruncă o privire la programele noastre de știință a datelor dacă ești interesat să obții expertiză.
Citiți: Programe de modele Python
Cuprins
Programul Python
O soluție de bază pentru găsirea unui număr perfect este să faci bucla peste 2 la numărul-1, să menții suma divizorilor săi corespunzători și să verifici dacă suma este egală cu numărul.
| n=int(input(„introduceți numărul”)) suma=1 pentru i în intervalul (2,n): dacă(n%i==0): sumă=sumă+i dacă(suma==n): print(n,”este un număr perfect”) altceva: print(n,”nu este un număr perfect”) |
Să parcurgem codul.
Mai întâi inițializam n cu intrarea utilizatorului și îl introducem într-un număr întreg, deoarece implicit intrarea utilizatorului este citită ca șir în python. Trebuie să verificăm dacă n este un număr perfect sau nu. Rețineți că inițializam suma cu 1, deoarece 1 este un divizor adecvat pentru toate numerele întregi (excluzând zero), astfel încât să putem exclude o iterație în buclă și să începem direct de la 2.
Facem bucla peste 2 la numărul-1 și adunăm numerele întregi pentru a însumați dacă este un divizor adecvat. Și în sfârșit, când ieșim din buclă verificăm dacă suma obținută este egală cu numărul sau nu. O bucată de tort, nu?
Mică versiune optimizată
După o rulare uscată peste programul de mai sus, s-ar putea să avem o întrebare dacă îl putem optimiza? Ei bine, dar putem reduce numărul de iterații la numărul/2 fără a schimba algoritmul. Pentru că am avut ideea că un număr nu poate avea un divizor propriu mai mare decât numărul/2.
| n=int(input(„introduceți numărul”)) suma=1 pentru i în interval (2,n//2+1): dacă(n%i==0): sumă=sumă+i dacă(suma==n): print(n,”este un număr perfect”) altceva: print(n, „nu este un număr perfect”) |
Fragmentul de mai sus este aproape similar cu cel precedent, cu singura diferență de a bucla până la numărul/2. Rețineți că efectuăm o împărțire a întregului pentru a evita convertirea acestuia într-un tip float și facem buclă până la n//2+1 deoarece ultimul întreg din interval nu este luat în considerare în bucla Python.
Limitări
Când ni se cere să găsim numere perfecte într-un interval dat, atunci soluția noastră ar consuma timp proporțional cu numărul^2, adică, complexitatea timpului O(n²). Pentru că trebuie să facem bucla peste fiecare număr din intervalul dat și apoi să verificăm divizorii corespunzători pentru fiecare număr. Și puține numere satisfac condiția perfectă a numărului. De exemplu, numărul de numere perfecte din intervalul de la 0 la 1000 este doar 3 (6, 28, 496).
Există o soluție optimizată pentru aceasta în care nu trebuie să facem bucla peste toate elementele pentru a găsi divizori corespunzători, formula lui Euclid afirmă că 2 n −1(2 n − 1) este un număr perfect par unde ambele n, (2 n − 1) sunt numere prime. De exemplu, 6 satisface ecuația de mai sus cu n ca 2 și ambele 2, 2 2 − 1 (2 2 − 1 = 3) sunt numere prime. Dar nu putem răspunde dacă ni se cere să aflăm dacă există numere perfecte impare.
De asemenea, știm că fiecare limbă are o limită a gamei de numere întregi pe care le poate stoca. Cu această limitare, este posibil să nu avem o modalitate de a găsi cel mai mare număr perfect.
Toate aceste limitări se confruntă dacă numărul nostru de intrare este mare, dar dacă numărul nostru de intrare este mic, atunci soluția noastră inițială ar funcționa în mai puțin timp.
Citiți și: Cadrul Python pentru Dezvoltare Web
Concluzie
Am cunoscut definiția și am înțeles conceptul din spatele numărului perfect. Am parcurs o soluție de bază pentru a găsi un număr este un număr perfect sau nu. Și după ce am urmărit soluția inițială, am optimizat-o puțin prin reducerea numărului de iterații. Am trecut prin limitările algoritmului nostru și am discutat formula lui Euclid pentru găsirea numărului perfect par.
Acum că sunteți la curent cu programul Python pentru a verifica dacă un număr este un număr perfect sau nu. Încercați să scrieți singur codul și încercați să îl optimizați dacă găsiți iterații care se suprapun. De asemenea, încercați să construiți codul pentru a găsi numere perfecte în intervalul dat de numere.
Dacă sunteți curios să aflați despre python, știința datelor, consultați programul Executive PG în știința datelor de la IIIT-B și upGrad, care este creat pentru profesioniști care lucrează și oferă peste 10 studii de caz și proiecte, ateliere practice practice, mentorat cu experți din industrie , 1-la-1 cu mentori din industrie, peste 400 de ore de învățare și asistență profesională cu firme de top.
Explicați complexitățile programului Perfect Number în Python.
Se spune că un număr este un număr perfect dacă este egal cu suma divizorilor săi. Pentru a verifica dacă un număr este perfect sau nu, avem două abordări. Prima abordare este o abordare naivă în care complexitatea timpului este O(n2), deoarece repetăm „j” ori pentru fiecare „i” și verificăm divizorii acestuia.
A doua abordare este soluția optimizată în care complexitatea timpului este O(√n). Aici nu trebuie să repetăm fiecare număr. O putem concluziona direct folosind formula lui Euclid, care este:
2n−1(2n − 1), unde n și 2n sunt numere prime.
Cu toate acestea, această formulă nu funcționează pentru numerele perfecte impare și, prin urmare, trebuie să găsim o altă abordare pentru ele.
Care sunt limitările abordărilor Programului Perfect Number?
Ambele abordări sunt bune, dar doar într-o oarecare măsură. Niciuna dintre ele nu poate fi considerată abordarea perfectă din cauza unor aspecte tehnice. Limitările acestor abordări sunt următoarele:
1. Prima abordare și cea naivă este mai proastă deoarece consumă mult timp și memorie și are o complexitate temporală de O(n2). Acest lucru se datorează faptului că folosim o buclă imbricată și repetăm bucla interioară de n ori pentru fiecare element al buclei exterioare. Această abordare este naivă și va da TLE pentru valori mai mari ale lui n și, prin urmare, nu este recomandată.
2. Apoi avem o abordare optimizată care rezolvă problema în O(√n). Aceasta este o abordare bună, dacă nu intră în joc numerele perfecte impare. Nu putem verifica numerele perfecte impare cu această abordare, deoarece se bazează pe „formula lui Euclid pentru numere perfecte pare” care funcționează numai pentru numere perfecte pare.
Este Python potrivit pentru programarea competitivă?
Python a evoluat din C/C++ și chiar din Java și este considerat a fi cel mai potrivit limbaj pentru cercetare și dezvoltare. Dar când vine vorba de programare competitivă, majoritatea comunității de programare evită Python. Motivul fiind că Python este cel mai lent dintre aceste trei limbi.