[NWD] Największy wspólny dzielnik, NWD

Największy wspólny dzielnik (NWD) – to największa liczba, która dzieli dwie lub więcej innych liczb bez reszty. NWD jest używany w matematyce do upraszczania ułamków i rozwiązywania problemów związanych z podzielnością liczb.

Jednym z popularnych algorytmów obliczania NWD dwóch liczb jest algorytm Euklidesa.

Java – NWD – wprowadzenie

W tym materiale dowiesz się:

• Jak obliczyć NWD?
• Co to jest algorytm Euklidesa?
• Jak wygląda algorytm znajdujący NWD za pomocą odejmowania?
• Co to jest kalkulator NWD?

NWD – Największy wspólny dzielnik

NWD można obliczyć rozkładając liczby na czynniki pierwsze.

Rozkład liczby na czynniki pierwsze

1. Ustalamy czy liczba jest podzielna przez 2, jeśli tak obliczamy iloraz
2. Sprawdzamy, czy iloraz jest podzielny przez 2 i wykonujemy dzielenie powtarzając procedurę do chwili aż iloraz nie będzie podzielny przez 2
3. Jeśli liczba wyjściowa lub iloraz nie jest podzielny przez 2, kontynuujemy procedurę z liczbą 3 lub kolejnymi liczbami do momentu uzyskania ilorazu będącego liczbą pierwszą

➡ ZOBACZ 👉: Liczby pierwsze – Magia i Programowanie

Algorytm Euklidesa

Algorytm Euklidesa to jedna z najstarszych i najbardziej znanych metod obliczania największego wspólnego dzielnika (NWD) dwóch liczb całkowitych. Ten algorytm został nazwany na cześć starożytnego greckiego matematyka Euklidesa, choć sam algorytm był znany wcześniej.

Polega on na powtarzającym się dzieleniu większej liczby przez mniejszą liczbę i zastępowaniu większej liczby resztą z tego dzielenia, aż do momentu, gdy reszta stanie się równa zero. Wówczas ostatnia niezerowa reszta jest największym wspólnym dzielnikiem dwóch liczb.

Jak obliczyć NWD?

public int findNWD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

W powyższym rozwiązaniu mamy metodę, która przyjmuje dwie liczby całkowite a i b. Algorytm Euklidesa jest implementowany w pętli while dopóki b nie osiągnie zera. W każdej iteracji obliczamy resztę z dzielenia a przez b, a następnie zamieniamy a na b, a b na obliczoną resztę.

➡ ZOBACZ 👉: Iteracja, iteracje – powtarzanie w programowaniu vs Rekurencja ➿, Iteracja, iteracje
➡ ZOBACZ 👉: Pętla (for, while, do while, foreach) pętle

NWD za pomocą odejmowania

Algorytm znajdujący Największy Wspólny Dzielnik można dostarczyć na różne sposoby. Jeden z nich to implementacja za pomocą odejmowania. Algorytm polega na wielokrotnym odejmowaniu mniejszej z dwóch liczb od większej, aż obie liczby staną się równe.

public static int findNWD(int a, int b) {
    while (a != b) {
        if (a > b) {
            a -= b;
        } else {
            b -= a;
        }
    }
    return a;
}

NWD Kalkulator

Kalkulator największego wspólnego dzielnika to narzędzie, które pomaga obliczyć NWD dwóch lub więcej liczb całkowitych. Kalkulator NWD jest szczególnie przydatny w matematyce, algorytmach i rozwiązywaniu problemów związanych z liczbami całkowitymi.

W Javie taki kalkulator można stworzyć za pomocą poznanych wyżej metod.

Java – NWD – Podsumowanie

W tym materiale dowiedzieliśmy się czym jest największy wspólny dzielnik i jak go zaimplementować w Javie.
Jako kolejny krok warto zainteresować się algorytmem liczącym [NWW] Najmniejsza wspólna wielokrotność.