Algorytm Euklidesa służy do wyznaczania największego wspólnego dzielnika dowolnie wybranych dwóch liczb naturalnych. Został on opisany około 300 roku p.n.e. przez Euklidesa w dziele „Elementy” i jest jednym z najstarszych algorytmów wciąż pozostających w użyciu.
Pozwala on na wyznaczenie NWD, nie rozkładając liczb na czynniki pierwsze. Cały algorytm opiera się na poniższym założeniu:

Zasada działania:
- Użytkownik musi wprowadzić dwie liczby naturalne, do zmiennych a oraz b;
- do zmiennej c przypisujemy resztę z dzielenia a przez b;
- zmienną a zastępujemy wartością zmiennej b, a do b przypisujemy wartość c;
- jeżeli b = 0 to NWD = a, jeżeli nie przejdź do punktu 2.
Przykładowy program wykorzystujący algorytm Euklidesa (napisany w języku Pascal):
program NWD;
USES crt;
VAR
a,b,c:integer;
BEGIN
clrscr;
writeln('Podaj dwie liczby naturalne:');
readln(a);
repeat
writeln('Druga liczba musi być różna od 0:');
readln(b);
until b <> 0;
{obliczamy NWD}
repeat
c := a mod b;
a := b;
b := c;
until b = 0;
{wyświetlamy wynik}
writeln('NWD = ', a);
repeat until keypressed;
end.Przykład rozpisany: NWD(252, 105)
Zobaczmy algorytm w akcji na konkretnych liczbach. W każdym kroku większą liczbę zastępujemy resztą z dzielenia:
| Krok | a | b | a mod b |
|---|---|---|---|
| 1 | 252 | 105 | 42 |
| 2 | 105 | 42 | 21 |
| 3 | 42 | 21 | 0 |
Reszta wyszła zero, więc NWD(252, 105) = 21. Trzy dzielenia zamiast rozkładania obu liczb na czynniki pierwsze, i to jest cała elegancja tego algorytmu: liczby maleją bardzo szybko, więc nawet dla ogromnych wartości kroków jest niewiele (złożoność logarytmiczna).
Implementacje: iteracyjna i rekurencyjna
// C++ - wersja iteracyjna (petla while)
int nwd(int a, int b) {
while (b != 0) {
int c = a % b;
a = b;
b = c;
}
return a;
}
// C++ - wersja rekurencyjna, ten sam pomysl w dwoch liniach
int nwdRek(int a, int b) {
if (b == 0) return a;
return nwdRek(b, a % b);
}# Python - identyczna logika
def nwd(a, b):
while b != 0:
a, b = b, a % b
return a
print(nwd(252, 105)) # 21Bonus: NWW z NWD i praktyczne zastosowanie
Znając NWD, najmniejszą wspólną wielokrotność liczymy jednym wzorem: NWW(a, b) = a · b / NWD(a, b). Dla naszych liczb: 252 · 105 / 21 = 1260. A po co to wszystko w praktyce? Klasyczne zastosowanie to skracanie ułamków (licznik i mianownik dzielimy przez ich NWD), sprowadzanie ułamków do wspólnego mianownika (przez NWW) oraz kryptografia, gdzie rozszerzona wersja algorytmu Euklidesa pracuje w sercu RSA.
Wersje w Javie i C#
Java:
public class Main {
public static int nwd(int a, int b) {
while (b != 0) {
int c = a % b;
a = b;
b = c;
}
return a;
}
public static void main(String[] args) {
System.out.println(nwd(252, 105)); // 21
}
}C#:
using System;
class Program
{
static int Nwd(int a, int b)
{
while (b != 0)
{
int c = a % b;
a = b;
b = c;
}
return a;
}
static void Main()
{
Console.WriteLine(Nwd(252, 105)); // 21
}
}


// brak komentarzy — bądź pierwszy