Liczby Praktyczne

Opis Liczb

Liczba Praktyczna n to taka liczba naturalna dla której wszystkie liczby naturalne mniejsze od niej samej można uzyskać jako sumę dowolnych dzielników właściwych liczby n. W trakcie sumowania wybrany dzielnik można dodać tylko raz.

Przykład

Liczbą Praktyczną jest 12, ponieważ dzielniki właściwe tej liczby to: {1, 2, 3, 4, 6}. Kolejne wartości mniejsze od 12 można uzyskać następująco:

Uwaga

Jedyną nieparzystą liczbą Praktyczną jest 1. Jest to spowodowane faktem, że każda liczba nieparzysta ma tylko nieparzyste dzielniki. Z tego powodu nie jest możliwe uzyskanie sumy 2 dla każdej liczby nieparzystej.

Implementacja

Strategia

Na początku algorytm może odrzucić wszystkie liczby nieparzyste prócz 1. Jednak dla liczb parzystych na początek należałoby zebrać wszystkie dzielniki właściwe liczby. Następnie w pętli dla każdej mniejszej wartości od zadanej liczby sprawdzimy czy można zsumować dzielniki do tej wartości.

Podczas sumowania należy pamiętać, że należy sumować najpierw jak największe wartości, a potem coraz mniejsze. Dzięki temu zagwarantowane jest znalezienie odpowiedzi czy taka suma istnieje w czasie liniowym. Gdyby sumować od najmniejszych wartości póki można to mogłoby się okazać, że nie ma już możliwości dodania większego dzielnika.

Kod

Przedstawiona funkcja czyPraktyczna() sprawdza czy podana liczba a jest liczbą Praktyczną, a wynikiem jest wartość logiczna.

1. bool czyPraktyczna(int a) {
2.   if (a == 1)
3.     return true;
4.   if (a % 2 == 1)
5.     return false;
6.   vector<int> v;
7.   for (int i = a / 2; i >= 1; i--) {
8.     if (a % i == 0) {
9.       v.push_back(i);
10.     }
11.   }
12.   for (int i = a - 1; i >= 2; i--) {
13.     int k = i;
14.     for (int j = 0; j < v.size(); j++) {
15.       if (v[j] <= k) {
16.         k -= v[j];
17.       }
18.     }
19.     if (k != 0) {
20.       return false;
21.     }
22.   }
23.   return true;
24. }

(2. - 6.) Na początku algorytmu eliminowane są przypadki, gdy a jest nieparzyste. Następnie (7. - 12.) generowana jest lista dzielników właściwych a. Dzielniki są zapisywane od największego do najmniejszego. Ostatni etap polega na (13. - 23.) znalezieniu takiego i, aby nie można było do tej wartości wysumować dzielników właściwych. W każdej iteracji k jest przypisywana wartość do wysumowania. Potem dla każdego dzielnika o ile jest mniejszy od aktualnej wartości k to jest on odejmowany od k. Jeśli na koniec k jest różne od 0 oznacza to, że danej wartości nie można uzyskać.

Testowanie funkcji

Poniższy fragment kodu wypisuje wszystkie liczby Praktyczne z zakresu [1, 100]

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

• Kod źródłowy Implementacja