Liczby Niedoskonałe

Definicja

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.

Ciąg

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

Przykład

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 czyNiedoskonala(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 czyNiedoskonala(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ższa funkcja main() korzysta z napisanej funkcji, aby wypisać wszystkie liczby

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

• Kod źródłowy Implementacja
• Kod źródłowy Optymalizacja

Zadania

Definicja

Zadanie 1

Napisz funkcję niedoskonalosc(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.

Zadanie 2

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

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

1. 5
2. 14
3. 44

• Kod źródłowy Zadanie 1, 2