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.

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.

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 pytania3

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.

def isPerfect(n):
    # Napisz kod tutaj

Test #1

Test #2

Test #3

Argument

n = 28

Oczekiwany wynik

true