Perfect Number

Q: 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.

Q: 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.

Q: 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.

Q: Qual è la differenza tra numeri perfetti, abbondanti e difettivi?

Confronta la somma dei divisori propri con il numero. Se sono uguali, il numero è perfetto, come 28 . Se la somma è maggiore, il numero è abbondante, come 12 , i cui divisori hanno somma 16 . Se è minore, il numero è difettivo, come ogni numero primo, il cui unico divisore proprio è 1 .

PrincipianteMatematica e simulazione

+10

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

isPerfect(n: integer) → boolean

ninteger: l'intero positivo da verificare
Restituisceboolean: vero se n è uguale alla somma dei suoi divisori propri, falso altrimenti

Vincoli

1 ≤ n ≤ 10⁸

Esempi

Input: n = 28
Output: true
Spiegazione: I divisori propri di 28 sono 1, 2, 4, 7 e 14. La loro somma è 28, quindi 28 è perfetto.

Input: n = 12
Output: false
Spiegazione: I divisori propri di 12 sono 1, 2, 3, 4 e 6. La loro somma è 16, che supera 12.

Input: n = 1
Output: false
Spiegazione: 1 non ha alcun divisore proprio, quindi la somma è 0, non 1.

+16 test nascosti all’invio

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ù.

0 di 3 aperti

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 total su 0.
Fai variare d da 1 a n / 2.
Se n % d == 0, aggiungi d a total.
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 == n

Raccogli 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, restituisci false.
Imposta total su 1 e d su 2.
Mentre d * d ≤ n: se d divide n, aggiungi d e aggiungi anche n / d quando è diverso da d.
Passa al d successivo.
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 n stesso. La coppia 1 × n aggiunge n e poi ogni numero sembra avere una somma maggiore di n. Inizia il totale da 1 e la ricerca da 2.
Considerare 1 perfetto. Se il totale parte da 1, l’input 1 confronta 1 == 1. La somma dei suoi divisori propri è 0, quindi gestiscilo prima del ciclo.
Aggiungere due volte una radice quadrata. Per 16 i divisori propri sono 1, 2, 4 e 8, la cui somma è 15. Aggiungere 4 due volte dà 19.
Fermarsi a d * d < n. Così si salta del tutto la radice quadrata, quindi 4 in 16 non viene mai contato.
Ricavare il limite da una radice quadrata in virgola mobile. Con la precisione singola, o sopra 2^53 con la precisione doppia, la radice di un quadrato perfetto può risultare inferiore di un’unità e far perdere un divisore. Il test d * d ≤ n usa numeri interi e non presenta mai questo problema.

Domande frequenti4

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.

Qual è la differenza tra numeri perfetti, abbondanti e difettivi?

Confronta la somma dei divisori propri con il numero. Se sono uguali, il numero è perfetto, come 28. Se la somma è maggiore, il numero è abbondante, come 12, i cui divisori hanno somma 16. Se è minore, il numero è difettivo, come ogni numero primo, il cui unico divisore proprio è 1.

Python

def isPerfect(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

n = 28

Atteso

true