Programma Perfect Number in Python: come verificare se un numero è perfetto o no?

Pubblicato: 2021-01-29

introduzione

Un numero si dice perfetto se la somma dei suoi divisori propri (escluso il numero stesso) è uguale al numero.

Per avere un'idea migliore consideriamo un esempio, i divisori propri di 6 sono 1, 2, 3. Ora la somma di questi divisori è uguale a 6 (1+2+3=6), quindi 6 è detto numero perfetto . Considerando che se consideriamo un altro numero come 12, i divisori propri di 12 sono 1, 2, 3, 4, 6. Ora la somma di questi divisori non è uguale a 12, quindi 12 non è un numero perfetto.

La programmazione in Python è relativamente più semplice e divertente rispetto ad altri linguaggi grazie alla sua sintassi più semplice e alla buona leggibilità. Ora che abbiamo chiaro il concetto di numero perfetto, scriviamo un programma Python per verificare se un numero è un numero perfetto o meno. Costruiamo un codice Python per verificare se l'input dell'utente fornito è un numero perfetto o meno ed esploriamo il divertimento nella codifica con Python. Dai un'occhiata ai nostri programmi di scienza dei dati se sei interessato ad acquisire esperienza.

Leggi: Programmi Python Pattern

Sommario

Programma Python

Una soluzione di base per trovare un numero perfetto è eseguire il ciclo da 2 al numero-1, mantenere la somma dei suoi divisori propri e verificare se la somma è uguale al numero.

n=int(input("inserisci il numero"))
somma=1
per i nell'intervallo(2,n):
se(n%i==0):
somma=somma+i
se(somma==n):
print(n,"è un numero perfetto")
altro:
print(n,"non è un numero perfetto")

Esaminiamo il codice.

Per prima cosa stiamo inizializzando n con l'input dell'utente e lo digitiamo su un numero intero perché per impostazione predefinita l'input dell'utente viene letto come una stringa in python. Dobbiamo verificare se n è un numero perfetto o meno. Si noti che stiamo inizializzando la somma con 1 perché 1 è un divisore proprio per tutti gli interi (escluso lo zero), in modo da poter escludere un'iterazione nel ciclo e iniziare direttamente da 2.

Stiamo passando da 2 a numero-1 e aggiungendo gli interi alla somma se è un divisore corretto. E infine, quando usciamo dal ciclo, controlliamo se la somma ottenuta è uguale al numero o meno. Pezzo di torta vero?

Versione poco ottimizzata

Dopo aver eseguito un test a secco sul programma sopra, potremmo avere una domanda, possiamo ottimizzarlo? Bene, ma possiamo ridurre il numero di iterazioni a numero/2 senza modificare l'algoritmo. Perché abbiamo avuto l'idea che un numero non può avere un divisore proprio maggiore di numero/2.

n=int(input("inserisci il numero"))
somma=1
per i nell'intervallo(2,n//2+1):
se(n%i==0):
somma=somma+i
se(somma==n):
print(n,"è un numero perfetto")
altro:
print(n, “non è un numero perfetto”)

Lo snippet sopra è quasi simile al precedente, con l'unica differenza di scorrere fino al numero/2. Nota che stiamo eseguendo una divisione di interi per evitare di convertirlo in un tipo float e stiamo eseguendo un ciclo fino a n//2+1 perché l'ultimo numero intero nell'intervallo non è considerato nel ciclo python.

Limitazioni

Quando ci viene chiesto di trovare numeri perfetti in un dato intervallo, la nostra soluzione consumerebbe tempo proporzionale al numero^2 cioè, O(n²) complessità temporale. Perché abbiamo bisogno di scorrere ogni numero nell'intervallo dato e quindi verificare la presenza di divisori appropriati per ogni numero. E pochi numeri soddisfano la condizione del numero perfetto. Ad esempio, il numero di numeri perfetti nell'intervallo da 0 a 1000 è solo 3 (6, 28, 496).

C'è una soluzione ottimizzata per questo in cui non è necessario scorrere tutti gli elementi per trovare i divisori appropriati, la formula di Euclide afferma che 2 n −1(2 n − 1) è un numero perfetto pari dove sia n, (2 n − 1) è numeri primi. Ad esempio, 6 soddisfa l'equazione precedente con n come 2 ed entrambi 2, 2 2 − 1 (2 2 − 1 = 3) sono numeri primi. Ma non possiamo rispondere se ci viene chiesto di trovare se ci sono numeri perfetti dispari.

Inoltre, sappiamo che ogni lingua ha un limite all'intervallo di numeri interi che può memorizzare. Con questa limitazione, potremmo non avere un modo per trovare il numero perfetto più grande.

Tutte queste limitazioni vengono affrontate se il nostro numero di input è grande, ma se il nostro numero di input è piccolo, la nostra soluzione iniziale funzionerebbe in meno tempo.

Leggi anche: Framework Python per lo sviluppo Web

Conclusione

Conosciamo la definizione e abbiamo compreso il concetto alla base del numero perfetto. Abbiamo esaminato una soluzione di base per trovare un numero è un numero perfetto o meno. E dopo aver visto la soluzione iniziale, l'abbiamo ottimizzata un po' riducendo il numero di iterazioni. Abbiamo superato i limiti del nostro algoritmo e discusso la formula di Euclide per trovare il numero perfetto pari.

Ora che sei a conoscenza del programma Python per verificare se un numero è un numero perfetto o meno. Prova a scrivere il codice da solo e prova a ottimizzarlo se trovi iterazioni sovrapposte. Inoltre, prova a costruire il codice per trovare numeri perfetti nell'intervallo di numeri specificato.

Se sei curioso di conoscere Python, la scienza dei dati, dai un'occhiata all'Executive PG Program in Data Science di IIIT-B e upGrad, creato per i professionisti che lavorano e offre oltre 10 casi di studio e progetti, workshop pratici pratici, tutoraggio con esperti del settore , 1 contro 1 con mentori del settore, oltre 400 ore di apprendimento e assistenza al lavoro con le migliori aziende.

Spiega le complessità del programma Perfect Number in Python.

Un numero si dice perfetto se è uguale alla somma dei suoi divisori. Per verificare se un numero è perfetto o meno, abbiamo due approcci. Il primo approccio è un approccio ingenuo in cui la complessità temporale è O(n2) poiché stiamo iterando "j" volte per ogni "i" e verificando i suoi divisori.
Il secondo approccio è la soluzione ottimizzata dove la complessità temporale è O(√n). Qui non è necessario scorrere su ogni numero. Possiamo concluderlo direttamente usando la formula di Euclide che è:
2n−1(2n − 1), dove n e 2n sono numeri primi.
Tuttavia, questa formula non funziona per i numeri perfetti dispari e quindi dobbiamo trovare un altro approccio per loro.

Quali sono i limiti degli approcci del Perfect Number Program?

Entrambi questi approcci sono buoni, ma solo in una certa misura. Nessuno dei due può essere considerato l'approccio perfetto a causa di alcuni tecnicismi. I limiti di questi approcci sono i seguenti:

1. Il primo e ingenuo approccio è peggiore perché consuma molto tempo e memoria e ha una complessità temporale di O(n2). Questo perché stiamo usando un ciclo annidato e iterando il ciclo interno n volte per ogni elemento del ciclo esterno. Questo approccio è ingenuo e darà TLE per valori maggiori di n e quindi non è raccomandato.
2. Allora abbiamo un approccio ottimizzato che risolve il problema in O(√n). Questo è un buon approccio a meno che non entrino in gioco i numeri dispari perfetti. Non possiamo verificare la presenza di numeri perfetti dispari con questo approccio poiché si basa sulla "formula di Euclide per numeri perfetti pari" che funziona solo per numeri perfetti pari.

Python è adatto per la programmazione competitiva?

Python si è evoluto da C/C++ e persino da Java ed è considerato il linguaggio più adatto per scopi di ricerca e sviluppo. Ma quando si tratta di programmazione competitiva, la maggior parte della comunità di programmazione evita Python. Il motivo è che Python è il più lento tra questi tre linguaggi.