Wskazówka:
Algorytm utworzymy w oparciu o tożsamość:
NWD (a1, a2,... , an) = NWD (NWD (a1, a2,... , an-1), an),
podaną w zadaniu drugim.

Za największy wspólny dzielnik obieramy liczbę a1 , a następnie iteracyjnie obliczamy naj- większy wspólny dzielnik zapamiętanego wyniku oraz liczby ai dla kolejnych i = 2, 3, 4, ...., n. Prowadzi to do następującego rozwiązania zadania:

w ← a1
dla i = 2, 3, 4, ...., n wykonuj
w ← NWD (w, ai)
zwróć w i zakończ

Podane rozwiązanie jest poprawne także wtedy, gdy n jest równe 1.
Powrót do pytań