Liczby doskonałe

Liczby doskonałe – implementacje

W poprzednich wpisach omówiliśmy sobie czym są liczby pierwsze, a także jak rozkładać liczby na czynniki. Podaliśmy również implementacje jak takie liczby wyznaczać. Będąc w temacie liczb naturalnych, warto dowiedzieć się czym są liczby doskonałe.

Liczby doskonałe to takie liczby, których suma podzielników właściwych (poza nimi samymi) jest równa właśnie tej liczbie. Dzielnikiem właściwym nazywamy dzielnik, który dzieli daną liczbę bez reszty. Dla przykładu podzielnikami liczby 28 są 1, 2, 4, 7, 14, 28. Suma podzielników będzie więc równa: 1 + 2 + 4 + 7 + 14 = 28. Liczby doskonałe występują w zbiorze liczb naturalnych relatywnie rzadko i do tej pory nie znaleziono żadnego schematu w ich występowaniu.

Istnieją również liczby doskonałe drugiego stopnia. Są to liczby, których iloczyn dzielników liczby, poza nią samą, jest równy tej liczbie. Przykładem jest liczba 6: 1 * 2* 3 = 6. Jak sprawdzić, czy liczba jest doskonała? Poniżej omówimy algorytm, a potem przejdziemy do jego implementacji w C++, Javie oraz Pythonie.

Liczby doskonałe — algorytm

Na początek pobieramy liczbę naturalną n od użytkownika. Następnie dobrze jest stworzyć dwie zmienne pomocnicze. Jedna z nich będzie przechowywać sumę dzielników, a druga ich iloczyn. Dzięki temu załatwimy od razu dwie sprawy — sprawdzimy jednocześnie, czy liczba jest doskonała stopnia pierwszego i/lub drugiego. Kolejnym krokiem jest rozpoczęcie iteracji od jedynki do połowy liczby n. W ten sposób znajdziemy wszystkie jej dzielniki. Zwróć uwagę, że iterujemy do połowy liczby n, gdyż dzielenie przez więcej niż jej połowa nigdy nie da całkowitego wyniku. Sprawdzamy każdą iterowaną liczbę, czy jest dzielnikiem właściwym. Wykorzystujemy do tego operator modulo, który zwraca resztę z dzielenia. Powinna ona być równa 0. Jeżeli tak jest, to dodajemy liczbę do pierwszej zmiennej pomocniczej, a drugą zmienną pomocniczą mnożymy. Gdy iteracja się zakończy, sprawdzamy, czy zmienne pomocnicze są równe liczbie n. Następnie, zależnie od wyniku, zwracamy czy i jakiego stopnia liczba jest doskonała.

Powyższy algorytm możemy zaprezentować na schemacie blokowym poniżej. Operator %, jest wyżej wspomnianym działaniem, zwracającym resztę z dzielenia dwóch liczb:

Liczby doskonałe — implementacja C++, Java i Python

Skoro wiemy już jak sprawdzić, czy liczba jest doskonała, przejdźmy zatem do implementacji. Wcielimy w życie powyżej omówiony algorytm, korzystając z trzech popularnych języków programowania. Języki te dostępne są do wyboru na maturze z informatyki, więc możesz sprawdzić działanie programu w tym wybranym przez siebie.

C++

Java

Python

Liczby doskonałe — ciekawostki

  • Liczby doskonałe występują naprawdę, bardzo, bardzo rzadko. Do dzisiaj znaleziono tylko 43 takie liczby, z czego największa z nich ma aż 18 milionów cyfr.
  • Liczba 6 nazywana jest liczbą najdoskonalszą. Jest ona bowiem jedyną, znaną liczbą, która jest jednocześnie doskonała w stopniu pierwszym i drugim.
  • Wszystkie znalezione liczby doskonałe są parzyste.
  • Nie wiadomo, czy liczb doskonałych jest nieskończenie wiele.

Podsumowanie

W dzisiejszym wpisie skorzystaliśmy z pojęcia dzielników liczby, o którym przeczytasz dokładniej tutaj. Ten i inne algorytmy ułatwią Ci zdanie matury z informatyki. Listę wszystkich moich porad, znajdziesz w tym oto wpisie.

grupa wsparcia matura z informatyki
You Might Also Like
Dodaj komentarz

icon