Strona główna » Algorytmy » Artykuły » Dzielniki Dwóch Liczb
 

Dzielniki Dwóch Liczb

https://mattomatti.com/a0222

Zadanie

Dane są dwie liczby naturalne. Znajdź ich wszystkie dzielniki i wypisz. Podczas pisania algorytmu należy wykorzystać swoją wiedzę dotyczącą wyszukiwania dzielników jak również podzielności liczb.

Przykład

Przykładowo dla liczb 15 i 60 mamy 3 wspólne dzielniki: 1, 3, 5 oraz 15. W tym przypadku druga liczba to wielokrotność pierwszej, więc wspólnymi dzielnikami są wszystkie liczby mniejszej liczby.

Innym przykładem jest para liczb 15 i 33. W tym przypadku jedyni wspólnymi dzielnikami są 1 oraz 3. Wynika to z faktu, że 15 = 5·3·1, a 33 = 11·3·1.

Implementacja

Rozwiązanie proste

Proste rozwiązanie polega na wybraniu mniejszej liczby, a następnie przejrzeniu wszystkich liczb od 1 do mniejszej liczby włącznie. Takie rozwiązanie daje z 100% pewnością dobry wynik, ale nie jest optymalne, ponieważ sprawdza wszystkie możliwe rozwiązania. Oto przykładowy kod:

  1. vector<int> DzielnikiLiczb(int a, int b) {
  2.   int min = a < b ? a : b;
  3.   vector<int> wynik;
  4.   for (int i = 1; i <= min / 2; i++) {
  5.     if (a % i == 0 && b % i == 0) {
  6.       wynik.push_back(i);
  7.     }
  8.   }
  9.   return wynik;
  10. }

Wyszukiwanie dzielników polega na wybraniu każdej kolejnej liczby z zakresu, a następnie sprawdzeniu czy dzieli obydwie liczby. Po znalezieniu wartości zostaje ona dopisana na koniec listy wynikowej.

Rozwiązanie Optymalne

Proste rozwiązanie nie optymalizuje w żaden sposób procesu wykrywania dzielników. Po pierwsze należy zauważyć, że iloczyn wszystkich dzielników to Największy Wspólny Dzielnik (NWD) obydwu liczb. Innymi słowy wystarczy znaleźć dzielniki NWD(a, b). Drugą istotną sprawą jest optymalizacja procesu szukania dzielników. Wykorzystując obydwa algorytmy uzyska się optymalny kod.

Oto przykładowy kod funkcji DzielnikiLiczb(), który dla dwóch podanych liczb zwróci wszystkie ich wspólne dzielniki.

  1. vector<int> DzielnikiLiczb(int a, int b) {
  2.   int nwd = NWD(a, b);
  3.   return DzielnikiNiewlasciwe(nwd);
  4. }

Dzięki wykorzystaniu gotowych funkcji kod znacznie się upraszcza.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu, który wczytuje dwie liczby, a następnie wypisuje wszystkie ich wspólne dzielniki.

  1. int main() {
  2.   int a, b;
  3.   cout << "Podaj dwie liczby:\n a = ";
  4.   cin >> a;
  5.   cout << " b = ";
  6.   cin >> b;
  7.   vector<int> dzielniki = DzielnikiLiczb(a, b);
  8.   cout << "Wspolne dzielniki liczb to:\n";
  9.   for each (int dzielnik in dzielniki)
  10.   {
  11.     cout << dzielnik << " ";
  12.   }
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Napisz algorytm, który zwróci wspólne dzielniki dla dowolnej ilości liczb. Przykładowo dla liczb 15, 33 i 60 wynikiem jest 1 i 3.