Strona główna » Algorytmy » Teoria Liczb » Liczby Doskonałe
 

Liczby Doskonałe

https://mattomatti.com/a37

Definicja

Liczba doskonała jest liczbą naturalną, która jest sumą wszystkich swoich dzielników właściwych.

Wyjaśnienie

Dzielnik właściwy to taki dzielnik, który jest mniejszy od liczby, którą dzielimy.

Przykładowo weźmy liczbę 6, 6 = 3 + 2 + 1, więc jest liczbą doskonałą. Liczba 6 jest najmniejszą liczbą doskonałą. Po niej kolejną liczbą doskonałą jest 28, ponieważ 28 = 14 + 7 + 4 + 2 + 1.

Cel

Napisz program, który na wejściu otrzyma jedną dodatnią liczbę całkowitą, a na wyjście wypisze PRAWDA jeśli wprowadzona liczba jest doskonała, a w innym przypadku FAŁSZ. Przykładowo dla wprowadzonej liczby 496:

  1. PRAWDA

Implementacja

Metoda I sprawdzania

Przed rozpoczęciem pisania funkcji warto zauważyć, że skoro dzielniki mają być właściwe to znaczy, że nie żaden nie może być równy liczbie, która została wprowadzona czyli największy możliwy dziennik będzie połową liczby wprowadzonej.

  1. bool czyDoskonala(int n){
  2.   int suma = 0;
  3.   for (int i = 1; i <= n/2; i++)
  4.     if(n % i == 0)
  5.       suma += i;
  6.   return (suma == n);
  7. }

(1.) Funkcja przyjmuje jeden argument, którym jest liczba do sprawdzenia czy jest doskonała. Funkcja zwraca wartość typu bool. (2.) Deklarujemy zmienną suma, która będzie nam potrzebna do sumowania kolejnych składników. (3.) Sprawdzamy wszystkie liczby w przedziale i (4.) jeśli i-ta liczba jest dzielnikiem argumentu n to (5.) dodajemy ją do sumy. W ten sposób uzyskujemy sumę wszystkich składników. Pozostaje nam (6.) sprawdzić czy suma jest równa n i zwrócić wynik tego porównania.

Rozkład liczby

Z przyczyn testowych czy ciekawskich warto tak napisać tę funkcję, aby wypisała nam na ekran wszystkie dzielniki i na koniec ich sumę. Przykładowo dla liczby 28 zostanie wypisany jej rozkład:

  1. 14 + 7 + 4 + 2 + 1 = 28

Kod

Zauważmy, że jeden dzieli każdą liczbę naturalną, więc zmienna suma może mieć ustawioną wartość początkową 1 i możemy rozpocząć poszukiwania dzielników od 2. To uprości nam również napisanie funkcji, która wypisze wszystkie dzielniki.

  1. bool czyDoskonalaDowod(int n){
  2.   int suma = 1;
  3.   cout << "1";
  4.   for (int i = 2; i <= n/2; i++){
  5.     if(n % i == 0){
  6.       cout << " + " << i;
  7.       suma += i;
  8.     }
  9.   }
  10.   cout << " = " << suma << endl;
  11.   return (suma == n);
  12. }

(2.) Ustalamy suma na 1, więc (3.) możemy wypisać 1 na konsole jako dzielnik. (4.) Szukamy dzielników, ale tym razem w zakresie . (5.) Jeśli i dzieli n to (6.) wypisujemy dzielnik na ekran i (7.) zwiększamy suma o i. (9.) Na koniec wypisujemy sumą dzielników. (10.) Zwracamy wynik porównania suma z n.

Metoda II

Euler udowodnił, że każda liczba doskonała parzysta ma postać , gdzie jest liczbą pierwszą. Zachodzi tu jednoznaczna odpowiedniość z liczbami pierwszymi Mersenne'a.

Wykorzystując podane informacje napiszemy funkcję, która zwróci kolejne n liczb doskonałych wyprowadzonych przy pomocy metody Euklidesa. Będziemy tutaj potrzebowali funkcji, która sprawdzi czy liczba jest pierwsza:

  1. bool prime(int n, int o=2){
  2.   return (o<=sqrt(n)) ? (n%o==0) ? false : prime(n,++o) : true;
  3. }

Wyjaśnienie do kodu znajduje się w artykule o liczbach pierwszych.

Funkcja wypiszDoskonale() przyjmie jeden argument a, który określi ile kolejnych liczb doskonałych mamy wypisać. Funkcja nie zwraca nic, ponieważ liczby będziemy wypisywać bezpośrednio na ekran.

  1. void wypiszDoskonale(int a){
  2.   int pot2 = 2;
  3.   while (a > 0){
  4.     pot2*=2;
  5.     if(prime(pot2 - 1)){
  6.       cout << (pot2 - 1) * pot2 / 2 << endl;
  7.       a--;
  8.     }
  9.   }
  10. }

Testowanie programu

Poniższa funkcja main() wczyta od użytkownika liczbę, a następnie wypisze na ekran czy liczba jest dokonała razem z dowodem. W drugiej części program wypisze n liczb doskonałych na podstawie wczytanej liczby.

  1. int main () {
  2.   setlocale(LC_ALL, "");
  3.   int n;
  4.   cout << "Podaj liczbę, do sprawdzenia: ";
  5.   cin >> n;
  6.   cout << (czyDoskonalaDowod(n) ? "PRAWDA" : "FAŁSZ");
  7.   cout << "\n\nIle kolejnych liczb doskonałych wypisać? ";
  8.   cin >> n;
  9.   wypiszDoskonale(n);
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Dopisz funkcję czyDoskonalaDowod2() na podstawie czyDoskonalaDowod(), która wypisze dzielniki od największego do najmniejszego.

Zadanie 2

Dopisz funkcję wypiszDoskonale2() na podstawie wypiszDoskonale(), która rozpocznie wypisywanie liczb doskonałych od określonej liczby m. Nagłówek funkcji powinien wyglądać tak:

  1. void wypiszDoskonale2(int a, int od){

Gdzie a określa ile kolejnych liczb doskonałych większy lub równych od.

Zadanie 3

Dopisz kolejną funkcję wypiszDoskonaleEuklides(), która wypisze a kolejnych liczb doskonałych. na podstawie poniższej informacji:

Euklides znalazł sposób na obliczanie liczb doskonałych parzystych: należy sumować kolejne potęgi dwójki, aż któraś z sum okaże się liczbę pierwszą i wtedy należy ostatni dodany składnik pomnożyć przez przedostatni i otrzymamy liczbę doskonałą.