NWD - największy wspólny dzielnik

Najstarszy znany i stosowany dziś algorytm został opisany w starożytności perzez Euklidesa. Dotyczy wyznaczania największego wspólnego dzielnika NWD.

Algorytm Euklidesa wersja z odejmowaniem:

• podaj dwie liczby a i b
• jeśli a jest większe, zmniejsz a o b
• jeśli a jest mnijsze, zmniejsz b o a
• postępuj tak, dopóki a będzie różne od b
• wynikiem jest a

Procedura C++

int nwd(int a, int b){
    while (a != b) {
        if(a > b)
            a = a - b;
        else
            b = b - a;
    }

    return a;
}

Algorytm Euklidesa wersja z resztą z dzielenia:

1. Podaj a i b
2. Dopóki b ≠ 0, wykonuj:
   1.  pom ← b;
   2.  b ← a % b;
   3.  a ← pom;
3. Wynikiem jest a.

Procedura C++

int nwd(int a, int b){
    while (b != 0) {
        int pom = b;
        b = a % b;
        a = pom;
    }

    return a;
}

Porównanie algorytmów odejmowania i reszty z dzielenia

a = 39 i b = 12

NWD odejmowanie
a b 27 12 15 12 3 12 3 9 3 6 3 3 NWD: 3
NWD reszta z dzielenia
a b pom 12 3 12 3 0 3 NWD: 3

NWW - najmniejsza wspólna wielokrotność

Wspólna wielokrotność liczb a i b to każda liczba naturalna, która dzieli się przez a oraz b.

Aby obliczyć NWW danej liczby należy:

1. Rozłożyć liczby na iloczyn czynników pierwszych (instrukcja jak rozkładać na czynniki pierwsze)
2. Dla każdego czynnika sprawdzić ile razy wystąpił dla jednej i drugiej liczby. Wybrać większą wartość i tyle razy zapisać tę liczbę.
3. Wymnożyć wszystkie liczby z punktu poprzedniego.

56 = 2 ∗ 2 ∗ 2 ∗ 7

100 = 2 ∗ 2 ∗ 5 ∗ 5

Sprawdzamy, ile razy dany czynnik pierwszy został użyty w każdym z równań. Wybieramy największą wartość i tyle razy zapisujemy tę liczbę, czyli:
NWW(56,100) = 2 ∗ 2 ∗ 2 ∗ 5 ∗ 5 ∗ 7 = 1400

Algorytm wyznaczania NWW.

Nie istnieje algorytm na obliczanie NWW. Mimo to, dzięki występowaniu tej zależności: Możemy skorzystać z algorytmu Euklidesa w celu znalezienia największego wspólnego dzielnika NWD (wybieramy resztę z dzielenia).
Mając NWD łatwo policzymy NWW.

Program C++

#include <iostream>
using namespace std;
           
int nwd(int a, int b){   
    while (b != 0) {
        int pom = b;
        b = a % b;
        a = pom;
    }
    return a;
}

int nww(int a, int b) {
    return a*b/nwd(a, b);
}

int main() {

    int a = 56;
    int b = 100;

    cout << "największa wspólna wielokrotność: " << nww(a, b);
}