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

Dzielniki Liczby

https://mattomatti.com/a0216

Wstęp

Do wyszukania wszystkich dzielników danej liczby wystarczy pojedyncza pętla. W tym artykule zostały przedstawione różnice między dzielnikami właściwymi oraz niewłaściwymi jak różne algorytmy do wyszukiwania dzielników.

Definicja

Dzielnik liczby a to taka liczba b, która przy dzieleniu daje resztę 0. Przykładowo liczba a ma następujące dzielniki {1, 2, 3, 4, 6, 12}. Są to wszystkie dzielniki, które są nazywane niewłaściwymi. Wśród dzielników właściwych nie występuje dzielnik b równy a (czyli, gdy mają równą wartość). Oznacza to, że dzielniki właściwe liczby a = 12 to {1, 2, 3, 4, 6}. Choć oba zbiory różnią się jednym elementem to w niektórych rozwiązaniach będzie to powodować potrzebne dodatkowe warunki.

Implementacja

Dzielniki Właściwe

Najprostszy algorytm do wyszukiwania wszystkich dzielników polega na przejrzeniu wszystkich liczb od 1 do a. Jednak nawet jeśli liczba ma dzielnik 2 to nie będzie dzielnika większego od a/2. Oznacza to, że można ograniczyć zakres poszukiwań dzielników do [1, a/2]. Oczywiście a również należy dopisać na listę.

  1. static List<int> DzielnikiNiewlasciwe(int a) {
  2.   List<int> wynik = new List<int>();
  3.   for (int i = 1; i <= a / 2; i++) {
  4.     if (a % i == 0) {
  5.       wynik.Add(i);
  6.     }
  7.   }
  8.   if (a > 1) {
  9.     wynik.Add(a);
  10.   }
  11.   return wynik;
  12. }

Warunkiem na dodanie liczby a na listę jest to, że jest ona większa od jednego. Wynika to z faktu, że 1 będzie znalezione dla każdej liczby i dodane na listę. Taki algorytm jest odporny na podanie wartości mniejszych od 1.

Dzielniki Niewłaściwe

Dla porównania algorytm, który wyszukuje wszystkie dzielniki niewłaściwe. Różnica polega jedynie na pominięciu warunki dodawania danej wartości a.

  1. static List<int> DzielnikiWlasciwe(int a) {
  2.   List<int> wynik = new List<int>();
  3.   for (int i = 1; i <= a / 2; i++) {
  4.     if (a % i == 0) {
  5.       wynik.Add(i);
  6.     }
  7.   }
  8.   return wynik;
  9. }

Dzielniki Właściwe Szybciej

Zauważmy, że wybierając kolejno po jednej liczbie z lewej strony jak i z prawej strony to ich iloczyn jest równy liczbie a. Przykładowo dla 12 dzielnikami są {1, 2, 3, 4, 6, 12} i prawdą jest to, że 1·12 = 2·6 = 3·4 = 12. Oznacza to, że nie trzeba wyszukiwać, aż do połowy liczby. Granicę przesuwamy na pierwiastek kwadratowy liczby a. Teraz jeśli będziemy szukać dzielników w zakresie [1, sqrt(a)] to znajdziemy wszystkie w zakresie [sqrt(a), a]. Dla znalezionego dzielnika d obliczamy a/d, aby otrzymać większy dzielnik.

Z takim podejściem wiążą się jednak dwa problemy. Po pierwsze, dzielniki nie będą posortowane, ponieważ kolejno będą znajdowane {1, 12, 2, 6, 3, 4}. Dodatkowo należy zauważyć, że wstawiania na ślepo a/d może doprowadzić do umieszczenia na liście dwa razy pierwiastka kwadratowego liczby jeśli takowy istnieje np. dla 16.

W celu rozwiązania powyższych problemów najpierw zostaną wyznaczone wszystkie dzielniki z przedziału [1, sqrt(a)], a pozostałe zostaną wyznaczone poprzez dzielenie a przez kolejne wartości na liście idąc od prawej do lewej. Przykładowo dla liczby 12 wyznaczamy dzielniki {1, 2, 3}, a następnie dopisujemy na koniec kolejno 12/3 = 4, 12/2 = 6, 12/1 = 12. Na drugi problem jedynym rozwiązaniem jest sprawdzić czy wstawiana wartość w drugiej pętli nie jest równa pierwiastkowi liczby.

Oto przykładowa implementacja:

  1. static List<int> DzielnikiNiewlasciwe(int a) {
  2.   List<int> wynik = new List<int>();
  3.   for (int i = 1; i <= Math.Sqrt(a); i++) {
  4.     if (a % i == 0) {
  5.       wynik.Add(i);
  6.     }
  7.   }
  8.   for (int i = wynik.Count - 1; i >= 0; i--) {
  9.     if (a / wynik[i] != wynik[i]) {
  10.       wynik.Add(a / wynik[i]);
  11.     }
  12.   }
  13.   return wynik;
  14. }

Powyższy algorytm został podzielony na dwie pętli jedynie w celu uproszczenia zapisu. Algorytm można też napisać w jednej pętli (patrz zadanie 1).

Testowanie funkcji

Oto przykładowy fragment programu, który dla podanej liczby wypisze wszystkie jej dzielniki właściwe:

  1. static void Main(string[] args) {
  2.   Console.Write("Podaj liczbę\n a = ");
  3.   int a = Convert.ToInt32(Console.ReadLine());
  4.   List<int> wynik = DzielnikiNiewlasciwe(a);
  5.   Console.WriteLine("Dzielniki:");
  6.   foreach(int x in wynik) {
  7.     Console.Write("{0} ", x);
  8.   }
  9.   Console.ReadKey();
  10. }

Zadania

Zadanie 1

Napisz algorytm do szybkiego znajdowania dzielników właściwych przy pomocy jednej pętli.