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

Liczby Niedoskonałe

Liczby Niedoskonałe

Liczby Niedoskonała to taka liczba naturalna n, której suma dzielników jest mniejsza od podwojonej jej wartości σ(n) < 2n. Można znaleźć definicję, której warunek brzmi, że suma dzielników właściwych liczby n musi być mniejsza od n czyli s(n) < n.

Przykład

Pierwsze liczby Niedoskonałe to 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, ..

13 to liczba Niedoskonała, ponieważ jej dzielniki to 1 i 13, a 14 < 26. Bardziej złożonym przypadkiem jest 8, które dzieli się przez 1, 2, 4 i 8, ale 1 + 2 + 4 + 8 = 15 i jest to mniej niż 16.

Implementacja

Szukanie dzielników liczby nie jest zadaniem trudnym, dlatego warto się skupić na optymalizacji rozpisanej definicji. Poniżej został zamieszczony kod realizujący zadanie:

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

W powyższym przykładzie: (2.) deklarowana jest zmienna suma, gdzie będą dodawane kolejne znalezione dzielniki. Następnie (3. - 7.) w pętli są wyszukiwane dzielniki z przedziału [1, n], gdzie (4.) jeśli zostanie znaleziony dzielnik to (5.) jest on dodawany do suma. Końcowym wynikiem jest (8.) porównanie sumy i dwukrotności liczby n.

Optymalizacja

Jak wiadomo najmniejszą liczbą pierwszą jest 2. Dzielników można szukać w zakresie [1, n/2] i dodać n, ponieważ w zakresie (n/2, n) na pewno nie będzie dzielnika liczby. W tym momencie należy przyjrzeć się drugiej definicji i zauważyć, że dodanie n so sumy dzielników jest zbyteczne, bo wtedy wzór się upraszcza do s(n) < n, gdzie n to suma dzielników właściwych n.

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

Z punktu widzenie złożoności czasowej dalej pozostaje liniowa, ale takie rozwiązanie można uznać za efektywniejsze, ponieważ wykonuje o połowę mniej operacji dzielenia oraz dwa razy wolniej wyczerpuje zakres przechowywanych wartości suma.

Testowanie funkcji

Poniższ funkcja main() korzysta z napisanej funkcji, aby wypisać wszystkie liczby

  1. int main() {
  2.   for (int i = 1; i <= 25; i++) {
  3.     if (isDeficient(i)) {
  4.       cout << i << endl;
  5.     }
  6.   }
  7.   system("pause");
  8.   return 0;
  9. }

Zadania

Definicja

Niedoskonałość jest definiowana jako różnice wartości n i sumy jej dzielników jej właściwych czyli n - s(n). Przykładowo niedoskonałość liczby 44 to 26, ponieważ 1 + 2 + 4 + 11 + 22 = 40.

Zadanie 1

Napisz funkcję deficiency(int n), która będzie przyjmowała argument całkowitoliczbowy n i dla podanej liczby zwróci niedoskonałość podanej liczby n. W przypadku, gdy podana liczba nie jest Niedoskonała to należy zwrócić -1.

W rozwiązaniu zadania nie korzystaj z funkcji isDeficient()!

Zadanie 2

Napisz funkcję deficiencyLevel(int from, int to, int level), która wypisze na ekran wszystkie liczby z przedziału [from, to], które mają niedoskonałość level.

Przykładowo dla zakresu [1, 100] i niedoskonałości 4 program wypisze:

  1. 5
  2. 14
  3. 44