Cel

Znajduje Największy Wspólny Dzielnik (GCD lub NWD) dwóch liczb.

Idea działania

Dla dwóch liczb całkowitych dodatnich $a$ i $b$ zachodzi równość:

Algorytm powtarzamy tak długo, aż reszta z dzielenia wyniesie 0. Wtedy ostatnia niezerowa reszta (lub liczba, przez którą dzieliliśmy w ostatnim kroku) jest szukanym NWD.

Stworzymy dodatkową zmienną tymczasową, i tak długo jak $b$ nie będzie 0, będziemy powtarzać

Kiedy użyć?

W przypadku tego algorytmu proste jest zauważenie potrzeby jego użycia, gdy taka jest obecna.

Implementacja

#include <iostream>
#include <cmath>
using namespace std;

int NWD(int & a, int & b) {
    int c;
    while(b != 0){
        c = a%b;
        a = b;
        b = c;
    }
    return a;
}

Złożoność

Czasowa: $O(n)$
Pamięciowa: O(log n)