Strona główna » Algorytmy » Teoria Liczb » Liczby Arytmetyczne
 

Liczby Arytmetyczne

https://mattomatti.com/a0008

Definicja

Liczba Arytmetyczna n to taka liczba naturalna, której średnia arytmetyczna dzielników jest liczbą całkowitą. Innymi słowy suma dzielników liczby n musi być wielokrotnością liczby dzielników.

Przykład

Najprostszą liczbą arytmetyczną jest 1, ponieważ suma dzielników to 1 i podzielone przez 1 otrzymamy liczbę całkowitą 1. Innym przykładem jest liczba 5, której suma dzielników to 1 + 5 = 6. Wynikiem dzielenia przez 2 jest 3. Liczbą arytmetyczną nie jest 9, ponieważ 1 + 3 + 9 = 13, a ten wynik nie jest podzielny przez 3.

Implementacja prosta

Do sprawdzenia czy dana liczba jest arytmetyczna służy funkcja isArithmetic(). Dla podanego argumentu n sprawdza czy liczba n jest liczbą arytmetyczną.

C++
C#
  1. bool isArithmetic(int n) {
  2.   long suma = 0;
  3.   int ile = 0;
  4.   for (int i = 1; i <= n; i++) {
  5.     if (n % i == 0) {
  6.       suma += i;
  7.       ile++;
  8.     }
  9.   }
  10.   return ((suma / ile) * ile == suma);
  11. }

Na początek należy zadeklarować (2.) zmienną do sumowania dzielników oraz (3.) zmienną zliczającą ile tych dzielników zostało zsumowanych. Następnie w (4. - 9.) pętli for szukane są dzielniki w zakresie [1, n]. (5.) W przypadku znalezienia (6.) wartość dzielnika jest dodawana do suma, a (7.) licznik ile zwiększany o 1. (10.) Na koniec należy sprawdzić czy suma dzielona przez ile. Z punktu matematycznego zapis ten powinien zawsze zwrócić prawdę, ale jest tutaj dzielenie całkowite, więc jeśli wynikiem nie jest liczba całkowita to po pomnożeniu przez ile nie wyjdzie suma.

Implementacja Pojemniejsza

W pierwszej implementacji prostej sumowane liczby mogą bardzo szybko przekroczyć maksymalny zakres zmiennej, nawet jeśli używany jest typ long long. Proponowane rozwiązanie rozwiązuje ten problem, ale działa przez to dwa razy dłużej.

Na początek warto zauważyć, że suma jest dzielona przez ile. Wynik jest fałszywy jeśli reszta jest różna od 0. W przypadku wyliczania reszty wiadomo, że (a1 + a2 + ... + ak) mod x = (((a1) mod x + a2) mod x + ... + ak) mod x. Algorytm na początku zliczy ile jest dzielników, a następnie będzie podczas sumowania będzie wyciągał resztę z dzielenia suma przez ile. Taki zabieg znacząco zwiększa zakres liczb dla których zostanie uzyskany poprawny wynik.

C++
C#
  1. bool isArithmetic(int n) {
  2.   int ile = 0;
  3.   for (int i = 1; i <= n; i++) {
  4.     if (n % i == 0) {
  5.       ile++;
  6.     }
  7.   }
  8.   long suma = 0;
  9.   for (int i = 1; i <= n; i++) {
  10.     if (n % i == 0) {
  11.       suma = (suma + i) % ile;
  12.     }
  13.   }
  14.   return (suma == 0);
  15. }

Tym razem funkcja na początek (2. - 7.) zlicza ile jest dzielników. Kolejny etap polega na (8. - 13.) zsumowaniu wszystkich dzielników, ale (11.) podczas zsumowania należy skorzystać z wspomnianej wcześniej zależności. Na koniec suma to reszta z dzielenie wszystkich dzielników przez ich ilość, więc (14.) należy zmienną przyrównać do 0.

Zadania

Zadanie 1

Napisz program, który zoptymalizuje proces poszukiwania dzielników. Wskazówka: Zakres poszukiwania można udoskonalić korzystając z faktu, że najmniejszą liczbą pierwszą jest 2.