Perfect Number
Un divisore proprio di n è un divisore positivo minore di n stesso. Un numero perfetto è uguale alla somma dei suoi divisori propri: 6 = 1 + 2 + 3. Ti viene dato un intero positivo n. Restituisci true se n è perfetto e false altrimenti.
Funzione
- ninteger
- l'intero positivo da verificare
- Restituisceboolean
- vero se n è uguale alla somma dei suoi divisori propri, falso altrimenti
Vincoli
1 ≤ n ≤ 108
Esempi
- Input
- n = 28
- Output
- true
- Spiegazione
- I divisori propri di
28sono1,2,4,7e14. La loro somma è28, quindi28è perfetto.
- Input
- n = 12
- Output
- false
- Spiegazione
- I divisori propri di
12sono1,2,3,4e6. La loro somma è16, che supera12.
- Input
- n = 1
- Output
- false
- Spiegazione
1non ha alcun divisore proprio, quindi la somma è0, non1.
Per approfondire
Ogni numero perfetto pari ha la forma 2^(p-1) × (2^p-1), dove 2^p-1 è primo. Riesci a elencare tutti i numeri perfetti minori di 10^8 usando questa formula, senza verificare ogni numero?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Scrivi i divisori propri di
28. Quali troveresti se considerassi solo i numeri fino a5?I divisori si presentano in coppie: se
ddividen, anchen / dlo divide. Un elemento di ogni coppia è al massimo√n.Inizializza il totale a
1, restituiscifalsepern == 1e itera condda2finchéd * d ≤ n. Aggiungiden / d, ma una sola volta quando sono uguali.
Soluzione
La definizione richiede una somma dei divisori e il ciclo più ovvio prova ogni candidato fino a n / 2. Per n = 10^8 si tratta di 5 × 10^7 divisioni. I divisori si presentano in coppie il cui prodotto è n, quindi puoi raccogliere entrambi gli elementi di ogni coppia cercando solo fino a √n, circa 10^4 passaggi.
Aggiungi ogni divisore proprio
Corretto, ma non termina sui test più grandi
Intuizione
Segui la definizione. Prova ogni d a partire da 1 e, quando n % d == 0, aggiungi d a un totale progressivo. Alla fine, confronta il totale con n. Per 28 il ciclo raccoglie 1, 2, 4, 7 e 14, e 1 + 2 + 4 + 7 + 14 = 28.
Puoi fermarti a n / 2. Un divisore diverso da n lascia un quoziente pari almeno a 2, quindi non è mai maggiore della metà di n. Questo limite gestisce anche n = 1: il ciclo viene eseguito zero volte, il totale rimane 0 e la risposta è false.
Dimezzare l’intervallo non cambia la crescita. Per n = 10^8 il ciclo viene comunque eseguito 5 × 10^7 volte, e questo accade per ogni input di quella dimensione, che sia divisore oppure no.
Algoritmo
- Imposta
totalsu0. - Fai variare
dda1an / 2. - Se
n % d == 0, aggiungidatotal. - Restituisci se
total == n.
def isPerfect(n):
total = 0
# No proper divisor of n is larger than n / 2.
for d in range(1, n // 2 + 1):
if n % d == 0:
total += d
return total == nRaccogli le coppie di divisori fino alla radice quadrata
Intuizione
Quando d divide n, anche n / d lo divide. Per 28 le coppie sono 1 × 28, 2 × 14 e 4 × 7. In ogni coppia, un elemento è al massimo √n, perché il prodotto di due numeri maggiori di √n è maggiore di n. Quindi una ricerca fino a √n incontra ogni coppia una volta, e aggiungi entrambi gli elementi man mano.
Due elementi richiedono attenzione. La coppia 1 × n include n stesso, che non è un divisore proprio: inizia il totale da 1 e la ricerca da 2. Questo valore iniziale è errato per n = 1, il cui unico divisore è il numero stesso, quindi restituisci prima false per questo caso. E quando n è un quadrato, la radice si accoppia con se stessa: per 36, 6 × 6 deve aggiungere 6 una sola volta, non due.
Scrivi il limite come d * d ≤ n, così resta espresso con numeri interi. Per n = 10^8 il ciclo si ferma a d = 10^4, quindi viene eseguito circa 10^4 volte invece di 5 × 10^7.
Algoritmo
- Se
n == 1, restituiscifalse. - Imposta
totalsu1edsu2. - Mentre
d * d ≤ n: seddividen, aggiungide aggiungi anchen / dquando è diverso dad. - Passa al
dsuccessivo. - Restituisci se
total == n.
def isPerfect(n):
if n == 1:
return False
total = 1 # 1 divides every n > 1; n itself does not count
d = 2
while d * d <= n:
if n % d == 0:
total += d
partner = n // d
if partner != d: # a square root pairs with itself: add it once
total += partner
d += 1
return total == n
Trappole e casi limite
Il trucco delle coppie è breve e ciascuno dei suoi bug cambia la somma esattamente di un divisore.
- Contare
nstesso. La coppia1 × naggiungene poi ogni numero sembra avere una somma maggiore din. Inizia il totale da1e la ricerca da2. - Considerare
1perfetto. Se il totale parte da1, l’input1confronta1 == 1. La somma dei suoi divisori propri è0, quindi gestiscilo prima del ciclo. - Aggiungere due volte una radice quadrata. Per
16i divisori propri sono1,2,4e8, la cui somma è15. Aggiungere4due volte dà19. - Fermarsi a
d * d < n. Così si salta del tutto la radice quadrata, quindi4in16non viene mai contato. - Ricavare il limite da una radice quadrata in virgola mobile. Con la precisione singola, o sopra
2^53con la precisione doppia, la radice di un quadrato perfetto può risultare inferiore di un’unità e far perdere un divisore. Il testd * d ≤ nusa numeri interi e non presenta mai questo problema.
Domande frequenti3
Qual è la complessità temporale del controllo di un numero perfetto?
Raccogliere le coppie di divisori fino a √n richiede tempo O(√n) e spazio O(1). Per n = 10^8 sono circa 10^4 passaggi. Verificare ogni candidato fino a n / 2 è O(n), circa 5 × 10^7 passaggi per lo stesso input.
Quanti numeri perfetti ci sono sotto 10^8?
Cinque: 6, 28, 496, 8128 e 33550336. Diventano rapidamente sempre più rare. La successiva, 8589869056, non entra nemmeno in un intero a 32 bit.
Esistono numeri perfetti dispari?
Nessuno lo sa. Tutti i numeri perfetti trovati finora sono pari. Le ricerche hanno escluso numeri perfetti dispari inferiori a 10^1500, ma non esiste alcuna dimostrazione che affermi che non possano esistere. La tua funzione deve basarsi sulla definizione, non sull’ipotesi che l’input sia pari.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isPerfect(n):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
n = 28
Output atteso
true