Kalkulator NWD i NWW to skrypt w języku Python, który oblicza Największy Wspólny Dzielnik oraz Najmniejszą Wspólną Wielokrotność dwóch liczb naturalnych.

Pełny kod programu znajdziesz na:

https://github.com/LukaszJedrasiak

Główny blok kalkulatora NWD i NWW jest dosyć prosty.

Copy to Clipboard
  • [1-2] Program pobiera od użytkownika dwie liczby: a i b (przydałoby się weryfikowanie, czy dane wejściowe faktycznie są liczbami naturalnymi),
  • [4, 6] Funkcja GenFirsts generuje listę z liczbami pierwszymi w zakresie od 2 do zadanej wartości. Wywoływana jest dwa razy – dla każdej z wprowadzonych przez użytkownika liczby.
  • [4, 6] Na bazie listy z liczbami pierwszymi funkcja GenDivisors tworzy kolejną tablicę – tym razem z wprowadzoną liczbą rozłożoną na czynniki pierwsze. Również wywoływana jest dwa razy, dla każdej z wprowadzonych przez użytkownika liczby.
  • [8] Funkcja GenCommonDivisors wyszukuje wspólne czynniki w obu wygenerowanych wcześniej listach oraz zwraca je w postaci kolejnej listy.
  • [10] Funkcja CountNWD oblicza wartość Największego Wspólnego Dzielnika na podstawie listy wspólnych dzielników.
  • [12] Funkcja CountNWW oblicza wartość Najmniejszej Wspólnej Wielokrotności na podstawie obliczonego wcześniej NWD.

Generator liczb pierwszych

Liczba pierwsza to taka liczba naturalna, która dzieli się bez reszty wyłącznie przez „1” oraz przez samą siebie.

Dwie zagnieżdżone pętle sprawdzają ten warunek dla każdej liczby naturalnej w zakresie od „2” do liczby podawanej za pomocą argumentu funkcji. Jeśli sprawdzana liczba podzieli się bez reszty przez liczbę naturalną mniejszą od siebie, flaga IsFirst otrzymuje wartość False, a pętla przerywa się. Jeśli się nie podzieli bez reszty to flaga IsFirst utrzymuje wartość True, a następnie sprawdzana liczba dodawana jest zwracanej tablicy.

Copy to Clipboard

Generator czynników pierwszych

Każdą liczbę naturalną można przedstawić za pomocą iloczynu pewnych liczb pierwszych, czyli tzw. czynników pierwszych. Innymi słowy, czynnik pierwszy to taka liczba pierwsza, która dzieli bez reszty daną liczbę naturalną.

Korzystając z wygenerowanej wcześniej listy liczb pierwszych funkcja sprawdza każdą z nich po kolei, czy dzieli bez reszty liczbę podaną w argumencie funkcji. Jeśli tak, to sprawdzana liczba pierwsza dołączana jest do zwracanej przez funkcję listy czynników pierwszych. Dzielenie przez daną liczbę pierwszą powtarzane jest dopóki reszta z dzielenia wynosi „0”. W momencie uzyskania innego wyniku pętla przechodzi do kolejnej liczby pierwszej z listy.

Copy to Clipboard

Wyszukiwanie części wspólnych na listach

To chyba najmniej elegancki fragment całego kodu, ale działa. Funkcja sprawdza po kolei obie wygenerowane wcześniej listy czynników pierwszych. Jeśli natrafi na te same wartości to kopiuje jedną z nich do nowej listy, a następnie „wymazuje” je z sprawdzanych list. „Wymazywanie” polega na zastąpieniu pierwotnych wartości różnymi znakami, aby nie zostały ponownie odczytane w kolejnych iteracjach.

Copy to Clipboard

Obliczanie NWD i NWW

Po wygenerowaniu listy wspólnych czynników pierwszych dla obu wprowadzonych liczb, obliczenie NWD i NWW jest już banalną operacją.

Największy Wspólny Dzielnik to nic innego, jak iloczyn wspólnych czynników pierwszych. Najmniejsza Wspólna Wielokrotność to po prostu iloczyn dwóch sprawdzanych liczb, podzielony przez NWD.

Copy to Clipboard