Perfect Number

Q: C jaka jest złożoność czasowa sprawdzania, czy liczba jest doskonała?

Zbieranie par dzielników do √n zajmuje O(√n) czasu i O(1) pamięci. Dla n = 10^8 to około 10^4 kroków. Testowanie każdego kandydata do n / 2 ma złożoność O(n) i dla tych samych danych wejściowych wymaga około 5 × 10^7 kroków.

Q: Ile liczb doskonałych jest mniejszych niż 10^8?

Pięć: 6 , 28 , 496 , 8128 i 33550336 . Szybko stają się coraz rzadsze. Kolejna, 8589869056 , nie mieści się nawet w 32-bitowej liczbie całkowitej.

Q: Czy istnieją nieparzyste liczby doskonałe?

Nikt nie wie. Każda dotychczas znaleziona liczba doskonała jest parzysta. Poszukiwania wykluczyły istnienie nieparzystych liczb doskonałych mniejszych niż 10^1500 , ale nie ma dowodu, że nie mogą istnieć. Twoja funkcja musi działać zgodnie z definicją, a nie na podstawie przypuszczenia, że dane wejściowe są parzyste.

Q: Jaka jest różnica między liczbami doskonałymi, obfitymi i niedoborowymi?

Porównaj sumę dzielników właściwych z daną liczbą. Równość oznacza liczbę doskonałą, taką jak 28 . Większa suma oznacza liczbę obfitą, taką jak 12 , której dzielniki sumują się do 16 . Mniejsza suma oznacza liczbę niedomiarową, taką jak każda liczba pierwsza, której jedynym dzielnikiem właściwym jest 1 .

PoczątkującyMatematyka i symulacja

+10

Dzielnik właściwy liczby n to dodatni dzielnik mniejszy od samej liczby n. Liczba doskonała jest równa sumie swoich dzielników właściwych: 6 = 1 + 2 + 3. Otrzymujesz dodatnią liczbę całkowitą n. Zwróć true, jeśli n jest doskonała, a w przeciwnym razie false.

Funkcja

isPerfect(n: integer) → boolean

ninteger: testowana dodatnia liczba całkowita
Zwracaboolean: true, jeśli n jest równe sumie swoich dzielników właściwych, false w przeciwnym razie

Ograniczenia

1 ≤ n ≤ 10⁸

Przykłady

Wejście: n = 28
Wyjście: true
Wyjaśnienie: Właściwe dzielniki liczby 28 to 1, 2, 4, 7 i 14. Ich suma wynosi 28, więc 28 jest liczbą doskonałą.

Wejście: n = 12
Wyjście: false
Wyjaśnienie: Właściwe dzielniki liczby 12 to 1, 2, 3, 4 i 6. Ich suma wynosi 16, czyli przekracza 12.

Wejście: n = 1
Wyjście: false
Wyjaśnienie: 1 nie ma żadnego właściwego dzielnika, więc suma wynosi 0, a nie 1.

+16 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Każda parzysta liczba doskonała ma postać 2^(p-1) × (2^p-1), gdzie 2^p-1 jest liczbą pierwszą. Czy potrafisz wypisać wszystkie liczby doskonałe mniejsze niż 10^8 za pomocą tego wzoru, bez testowania każdej liczby?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Definicja wymaga sumy dzielników, a oczywista pętla sprawdza każdego kandydata aż do n / 2. Dla n = 10^8 oznacza to 5 × 10^7 dzieleń. Dzielniki występują w parach, których iloczyn wynosi n, więc możesz zebrać oba elementy każdej pary, przeszukując liczby tylko do √n, czyli wykonując około 10^4 kroków.

Dodaj każdy właściwy dzielnik

Poprawne, ale nie kończy się na największych testach

Intuicja

Postępuj zgodnie z definicją. Sprawdź po kolei każdą wartość d, zaczynając od 1, a gdy n % d == 0, dodaj d do sumy bieżącej. Na końcu porównaj sumę z n. Dla 28 pętla uwzględnia 1, 2, 4, 7 i 14, a 1 + 2 + 4 + 7 + 14 = 28.

Możesz zakończyć na n / 2. Dzielnik inny niż n pozostawia iloraz wynoszący co najmniej 2, więc nigdy nie jest większy niż połowa n. To ograniczenie działa także dla n = 1: pętla wykonuje się zero razy, suma pozostaje równa 0, a odpowiedzią jest false.

Podzielenie zakresu na pół nie zmienia tempa wzrostu. Dla n = 10^8 pętla nadal wykonuje się 5 × 10^7 razy, i dzieje się tak dla każdego wejścia o takim rozmiarze, niezależnie od tego, czy jest dzielnikiem.

Algorytm

Ustaw total na 0.
Przejdź pętlą przez d od 1 do n / 2.
Jeśli n % d == 0, dodaj d do total.
Zwróć informację, czy 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

Zbieraj pary dzielników do pierwiastka kwadratowego

Intuicja

Gdy d dzieli n, to n / d również je dzieli. Dla 28 pary to 1 × 28, 2 × 14 i 4 × 7. W każdej parze jeden element jest nie większy niż √n, ponieważ iloczyn dwóch liczb większych od √n jest większy niż n. Wystarczy więc przeszukać liczby do √n, aby znaleźć każdą parę dokładnie raz, i dodawać oba jej elementy.

Na dwa elementy trzeba uważać. Para 1 × n zawiera samo n, które nie jest właściwym dzielnikiem: zacznij sumę od 1, a przeszukiwanie od 2. Ten początek jest nieprawidłowy dla n = 1, którego jedynym dzielnikiem jest ono samo, więc najpierw zwróć dla niego false. A gdy n jest kwadratem, pierwiastek tworzy parę z samym sobą: dla 36 para 6 × 6 powinna dodać 6 raz, a nie dwa razy.

Zapisz ograniczenie jako d * d ≤ n, dzięki czemu pozostajesz w liczbach całkowitych. Dla n = 10^8 pętla kończy się przy d = 10^4, więc wykonuje około 10^4 iteracji zamiast 5 × 10^7.

Algorytm

Jeśli n == 1, zwróć false.
Ustaw total na 1, a d na 2.
Gdy d * d ≤ n: jeśli d jest dzielnikiem n, dodaj d, a także n / d, jeśli różni się od d.
Przejdź do następnej wartości d.
Zwróć informację, czy 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

Pułapki i przypadki brzegowe

Sztuczka z parami jest krótka, a każdy z jej błędów zmienia sumę dokładnie o jeden dzielnik.

Liczenie samego n. Para 1 × n dodaje n, przez co każda liczba wygląda tak, jakby jej suma była większa od n. Zacznij sumę od 1, a wyszukiwanie od 2.
Uznawanie 1 za liczbę doskonałą. Gdy suma zaczyna się od 1, dla wejściowej wartości 1 porównanie ma postać 1 == 1. Suma jej właściwych dzielników wynosi 0, więc obsłuż ten przypadek przed pętlą.
Dodawanie pierwiastka kwadratowego dwukrotnie. Dla 16 właściwe dzielniki to 1, 2, 4 i 8, a ich suma wynosi 15. Dwukrotne dodanie 4 daje 19.
Zatrzymywanie się przy d * d < n. To pomija pierwiastek kwadratowy, więc 4 dla 16 nigdy nie zostaje uwzględnione.
Wyznaczanie granicy na podstawie pierwiastka kwadratowego w liczbie zmiennoprzecinkowej. W przypadku pojedynczej precyzji lub dla liczb większych niż 2^53 w podwójnej precyzji pierwiastek z kwadratu doskonałego może być zaokrąglony w dół o jeden, przez co dzielnik zostanie pominięty. Test d * d ≤ n operuje na liczbach całkowitych i nigdy nie sprawia tego problemu.

Najczęstsze pytania4

C jaka jest złożoność czasowa sprawdzania, czy liczba jest doskonała?

Zbieranie par dzielników do √n zajmuje O(√n) czasu i O(1) pamięci. Dla n = 10^8 to około 10^4 kroków. Testowanie każdego kandydata do n / 2 ma złożoność O(n) i dla tych samych danych wejściowych wymaga około 5 × 10^7 kroków.

Ile liczb doskonałych jest mniejszych niż 10^8?

Pięć: 6, 28, 496, 8128 i 33550336. Szybko stają się coraz rzadsze. Kolejna, 8589869056, nie mieści się nawet w 32-bitowej liczbie całkowitej.

Czy istnieją nieparzyste liczby doskonałe?

Nikt nie wie. Każda dotychczas znaleziona liczba doskonała jest parzysta. Poszukiwania wykluczyły istnienie nieparzystych liczb doskonałych mniejszych niż 10^1500, ale nie ma dowodu, że nie mogą istnieć. Twoja funkcja musi działać zgodnie z definicją, a nie na podstawie przypuszczenia, że dane wejściowe są parzyste.

Jaka jest różnica między liczbami doskonałymi, obfitymi i niedoborowymi?

Porównaj sumę dzielników właściwych z daną liczbą. Równość oznacza liczbę doskonałą, taką jak 28. Większa suma oznacza liczbę obfitą, taką jak 12, której dzielniki sumują się do 16. Mniejsza suma oznacza liczbę niedomiarową, taką jak każda liczba pierwsza, której jedynym dzielnikiem właściwym jest 1.

Python

def isPerfect(n):
    # Napisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

n = 28

Oczekiwane

true