Liczba doskonała w Pythonie

powrót

Liczba doskonała to taka liczba naturalna, której suma naturalnych dzielników mniejszych od niej jest równa tej liczbie.

Przykład

Takimi liczbami są: 6, 28, 496, 8128, 33550336, 8589869056, 137438691328, ...

Przeanalizujmy liczby: 6 i 28:

$$D_6=\{1, 2, 3\}\ ,6 = 1 + 2 + 3$$$$D_{28}=\{1, 2, 4, 7, 14\},\ 28 = 1 + 2 + 4 + 7 + 14$$

Strategia algorytmu

Dla zadanej dodatniej liczby naturalnej n wykonamy $$\sqrt{n}$$ operacji. Skorzystamy z faktu, że jeżeli liczba k jest dzielnikiem liczby n, to tym dzielnikiem musi być także liczba n/k, gdzie $$k \leqslant \sqrt{n}$$ np. jeśli liczba 3 jest dzielnikiem liczby 24, to jej dzielnikiem jest także liczba 8, bo $$24/3 = 8.$$

#*****************www.algorytm.edu.pl****************
# *******************algorytm.edu.pl**************************
# zmienna suma będzie przechowywać sumę 
def czy_doskonala(liczba):
    suma = 1 # każda liczba dzieli się przez jeden
    k = 2 # k przyjmuje kolejne wartości z przedziału [2..sqrt(liczba))
    while k*k < liczba:
        if liczba % k == 0: # jeśli k jest dzielnikiem liczby liczba
            suma += k + liczba/k # to zwiększ wartość zmiennej suma o dwa dzielniki
        k += 1
    if k*k == liczba: # jeśli liczba jest kwadratowa
        suma += k   # to zwiększ wartość suma o dzielnik k
    return suma == liczba

# *******************główna część programu********************
liczba = int(input("Podaj liczbę: "))
if czy_doskonala(liczba):
    print(f"Liczba {liczba} jest doskonała")
else:
    print(f"Liczba {liczba} nie jest doskonała")