Algorytm Euklidesa znajduje największy wspólny dzielnik (NWD) dwóch liczb, zastępując większą z nich resztą z dzielenia przez mniejszą, aż reszta wyniesie zero: dla 252 i 105 wystarczą trzy dzielenia, a wynik to 21. Starszą wersję tego samego pomysłu, z wielokrotnym odejmowaniem, Euklides opisał w księdze VII “Elementów” około 300 roku p.n.e. Wersja z odejmowaniem potrzebuje dla tej pary pięciu kroków, a dla 1000 i 1 aż 999. Najmniejszą wspólną wielokrotność (NWW) liczy się potem jednym wzorem z NWD. W Pythonie całość załatwia math.gcd(252, 105), w C++17 std::gcd z nagłówka <numeric>, a JavaScript nie ma funkcji wbudowanej i trzeba ją napisać samemu.
Co to jest NWD i na czym polega algorytm Euklidesa
NWD, czyli największy wspólny dzielnik, to największa liczba naturalna, która dzieli obie liczby bez reszty. Dla 252 i 105 jest to 21, bo 252 = 21 · 12 i 105 = 21 · 5, a liczby 12 i 5 nie mają już wspólnego dzielnika większego od 1. Takie liczby nazywa się względnie pierwszymi.
Cała metoda opiera się na jednej obserwacji: liczba, która dzieli a i b, dzieli też ich różnicę a − b. Dlatego NWD(252, 105) jest równe NWD(147, 105), NWD(42, 105) i tak dalej. Liczby maleją, a wspólny dzielnik zostaje ten sam, aż obie liczby się zrównają albo jedna z nich spadnie do zera.
Euklides zapisał to w “Elementach”, w księdze VII. Twierdzenie 2 w wydaniu D. E. Joyce’a brzmi: “znaleźć największą wspólną miarę dwóch danych liczb, które nie są względnie pierwsze”. Twierdzenie 1 opisuje ten sam proces dla liczb względnie pierwszych, kiedy odejmowanie kończy się na jedynce. Liczby są u Euklidesa odcinkami (AB, CD), a “mierzyć” znaczy dzielić bez reszty. Na zdjęciu otwierającym tekst widać pierwsze drukowane wydanie “Elementów” (Erhard Ratdolt, Wenecja 1482) ze zbiorów Biblioteki Narodowej Francji. Fot. Zythème, Wikimedia Commons, licencja CC0.
Algorytm Euklidesa z odejmowaniem
Wersja z odejmowaniem jest najbliższa oryginałowi: dopóki liczby są różne, od większej odejmij mniejszą. Gdy się zrównają, wynik to NWD. Dla pary 252 i 105 wygląda to tak:
- 252 − 105 = 147, para (147, 105)
- 147 − 105 = 42, para (42, 105)
- 105 − 42 = 63, para (42, 63)
- 63 − 42 = 21, para (42, 21)
- 42 − 21 = 21, para (21, 21), koniec: NWD = 21
Ta wersja ma dwie słabości. Pierwsza to liczba kroków, gdy jedna liczba jest dużo większa od drugiej: dla 1000 i 1 trzeba 999 odejmowań. Druga to zero. Dla pary (5, 0) pętla nigdy się nie kończy, bo odejmowanie zera nic nie zmienia. Dlatego w programach używa się prawie zawsze wersji z resztą z dzielenia.
Algorytm Euklidesa z dzieleniem (z resztą, modulo)
Wersja z dzieleniem zastępuje parę (a, b) parą (b, a mod b), gdzie a mod b to reszta z dzielenia a przez b. Kończy się, gdy reszta wyniesie zero. Wtedy NWD to ostatni niezerowy dzielnik. Dla 252 i 105:
- 252 = 2 · 105 + 42, para (105, 42)
- 105 = 2 · 42 + 21, para (42, 21)
- 42 = 2 · 21 + 0, koniec: NWD = 21
Obie wersje liczą to samo. Jedno dzielenie z resztą zastępuje całą serię odejmowań: 252 − 105 − 105 = 42, czyli dokładnie 252 mod 105. Iloraz mówi, ile razy wersja z odejmowaniem odjęłaby tę samą liczbę. Wersja z resztą działa też dla zera: NWD(7, 0) = 7, bo pętla kończy się od razu.
Frontend Master 2026 · Kodożercy
Od pierwszej linijki kodu do deploy
Frontend Master 2026 to pakiet sześciu kursów Kodożerców z HTML, CSS, JavaScriptu i Git. Polskie wideo, prawdziwe projekty, fundamenty, dzięki którym przestajesz trafiać w ciemno.
Sprawdź pakiet →
Odejmowanie czy reszta z dzielenia: ile kroków potrzeba
Jeśli większą liczbę ustawimy jako pierwszą, wersja z resztą z dzielenia nie potrzebuje więcej kroków niż wersja z odejmowaniem, poza przypadkiem dwóch równych liczb. Zwykle potrzebuje ich dużo mniej. Policzyliśmy to dla sześciu par liczb. Dla 123456 i 789 wersja z odejmowaniem wykonuje 172 kroki, a wersja z resztą 6. Dla 1000 i 1 jest to 999 kroków wobec jednego.
Najgorszy przypadek: kolejne liczby Fibonacciego (twierdzenie Lamégo)
Najwięcej dzieleń potrzebują dwie kolejne liczby Fibonacciego. Przy parze 89 i 55 wszystkie ilorazy poza ostatnim wynoszą 1, więc każdy krok zmniejsza liczby tylko o jeden wyraz ciągu: 89, 55, 34, 21, 13, 8, 5, 3, 2, 1. Ostatnie dzielenie, 2 przez 1, daje iloraz 2 i resztę 0. Dlatego na wykresie obie wersje mają tu po 9 kroków. Więcej o samym ciągu piszemy w tekście o ciągu Fibonacciego.
Gabriel Lamé udowodnił to w notatce przedstawionej na posiedzeniu Akademii Nauk w Paryżu 28 października 1844 roku (Comptes rendus, t. XIX, s. 867–870). Jego twierdzenie mówi, że liczba dzieleń jest zawsze mniejsza niż pięciokrotność liczby cyfr mniejszej z dwóch liczb. Lamé liczył dzielenia do momentu, gdy reszta wynosi 1. Jeśli doliczyć też ostatnie dzielenie z resztą 0, tak jak robi nasz kod, granica brzmi “nie więcej niż”: para 144 i 89 potrzebuje dokładnie 10 dzieleń przy dwucyfrowej liczbie 89.
W praktyce oznacza to, że liczba kroków rośnie jak logarytm z mniejszej liczby. Dwie liczby po 18 cyfr wymagają najwyżej 90 dzieleń. Tak zachowują się algorytmy o złożoności logarytmicznej, które opisujemy w przeglądzie rodzajów algorytmów i ich złożoności.
NWW z pomocą NWD: wzór i przykład
Najmniejszą wspólną wielokrotność dwóch liczb dodatnich liczy się ze wzoru NWW(a, b) = a · b / NWD(a, b). Dla 252 i 105: 252 · 105 = 26 460, a 26 460 / 21 = 1260. Wzór wynika z tego, że iloczyn obu liczb zawiera wspólną część dwa razy, a NWD usuwa jedną z nich.
W językach ze stałym rozmiarem liczb, jak C++ czy Java, kolejność działań ma znaczenie. Dla 60 000 i 90 000 iloczyn to 5 400 000 000, czyli więcej niż mieści 32-bitowy int (maksymalnie 2 147 483 647). Sam wynik jest mały: NWD to 30 000, a NWW to 180 000. Wystarczy najpierw podzielić, a potem pomnożyć: a / nwd(a, b) * b, czyli 2 · 90 000.
Jak obliczyć NWD i NWW bez komputera: rozkład na czynniki pierwsze
W szkole NWD i NWW liczy się zwykle z rozkładu na czynniki pierwsze. 252 = 2 · 2 · 3 · 3 · 7, a 105 = 3 · 5 · 7. NWD to iloczyn czynników wspólnych: 3 · 7 = 21. NWW to iloczyn wszystkich czynników w najwyższych potęgach: 2 · 2 · 3 · 3 · 5 · 7 = 1260. Jak rozpoznać liczbę pierwszą i rozłożyć liczbę na czynniki, pokazujemy w tekście o liczbach pierwszych i sicie Eratostenesa.
Ta metoda jest wygodna dla małych liczb, ale nie skaluje się. Rozłożenie dużej liczby na czynniki jest trudne, a metoda Euklidesa w ogóle tego nie potrzebuje. Dlatego komputery liczą NWD Euklidesem.
Algorytm Euklidesa w Pythonie
W Pythonie cały algorytm mieści się w kilku linijkach. Własne funkcje w tym tekście zakładają liczby dodatnie: dla ujemnych trzeba najpierw wziąć wartości bezwzględne (abs), a NWW z zerem obsłużyć osobno. Funkcje wbudowane robią to same. Poniżej wersja z odejmowaniem:
def nwd_odejmowanie(a, b):
while a != b:
if a > b:
a = a - b
else:
b = b - a
return a
print(nwd_odejmowanie(252, 105))
print(nwd_odejmowanie(1000, 1))
Wynik w konsoli (Python 3.14.3):
21
1
Wersja z resztą z dzielenia, iteracyjnie i rekurencyjnie, razem z NWW:
def nwd(a, b):
while b != 0:
a, b = b, a % b
return a
def nwd_rek(a, b):
if b == 0:
return a
return nwd_rek(b, a % b)
def nww(a, b):
return a // nwd(a, b) * b
print(nwd(252, 105), nwd_rek(252, 105))
print(nww(252, 105))
print(nwd(18, 48), nwd(17, 5))
Wynik w konsoli (Python 3.14.3):
21 21
1260
6 1
Wersja rekurencyjna wywołuje samą siebie z mniejszą parą liczb, aż dojdzie do b == 0. Ten wzorzec szerzej opisujemy w tekście o algorytmach rekurencyjnych. Dla 18 i 48 kolejność nie ma znaczenia, bo pierwszy obrót pętli zamienia liczby miejscami.
math.gcd, math.lcm i nowy moduł math.integer
W praktyce w Pythonie nie trzeba pisać własnej funkcji. Dokumentacja modułu math podaje, że math.gcd() jest od Pythona 3.5, a math.lcm() i obsługa wielu argumentów w gcd() od 3.9.
import math
print(math.gcd(252, 105))
print(math.lcm(252, 105))
print(math.gcd(252, 105, 84))
print(math.gcd(-12, 18), math.gcd(0, 7), math.gcd(0, 0))
print(math.lcm(4, 6, 10), math.lcm(0, 5))
Wynik w konsoli (Python 3.14.3, ten sam w 3.15.0):
21
1260
21
6 7 0
60 0
Python 3.15, wydany 9 października 2026 roku, dodał moduł math.integer z funkcjami dla liczb całkowitych. Według dokumentacji math.gcd i math.lcm są od tej wersji “miękko przestarzałe” (soft deprecated): działają dalej, bez ostrzeżeń, ale nowy kod ma używać math.integer.gcd i math.integer.lcm.
import math.integer
print(math.integer.gcd(252, 105))
print(math.integer.lcm(252, 105))
Wynik w konsoli (Python 3.15.0):
21
1260
Jeśli kod ma działać także na starszych wersjach Pythona, math.gcd zostaje bezpiecznym wyborem. Jeśli dopiero wybierasz język do nauki algorytmów, porównanie Pythona i Javy pomoże zdecydować.
Algorytm Euklidesa w C++: pętla, rekurencja i std::gcd
W C++ kod wygląda prawie tak samo, a od C++17 jest też w bibliotece standardowej. cppreference podaje, że std::gcd i std::lcm są w nagłówku <numeric> od C++17.
#include <iostream>
#include <numeric>
long long nwd_odejmowanie(long long a, long long b) {
while (a != b) {
if (a > b) a -= b;
else b -= a;
}
return a;
}
long long nwd(long long a, long long b) {
while (b != 0) {
long long r = a % b;
a = b;
b = r;
}
return a;
}
long long nwd_rek(long long a, long long b) {
return b == 0 ? a : nwd_rek(b, a % b);
}
long long nww(long long a, long long b) {
return a / nwd(a, b) * b;
}
int main() {
std::cout << nwd_odejmowanie(252, 105) << ' ' << nwd(252, 105) << ' '
<< nwd_rek(252, 105) << '\n';
std::cout << nww(252, 105) << '\n';
std::cout << std::gcd(252, 105) << ' ' << std::lcm(252, 105) << '\n';
std::cout << std::gcd(-12, 18) << ' ' << std::gcd(0, 0) << '\n';
}
Wynik w konsoli (GCC 15.2, -std=c++17 -O2 -Wall):
21 21 21
1260
21 1260
6 0
Funkcja nww dzieli przed mnożeniem, z powodu opisanego wyżej przy NWW. std::gcd dla liczb ujemnych zwraca NWD ich wartości bezwzględnych, a dla dwóch zer zwraca zero. Według cppreference std::lcm ma niezdefiniowane zachowanie, gdy wynik nie mieści się w typie, więc przy dużych liczbach trzeba dobrać typ z zapasem.
NWD w JavaScripcie: pętla, rekurencja i BigInt
JavaScript nie ma wbudowanej funkcji NWD, więc trzeba ją napisać. Zwykłe liczby w JS są zmiennoprzecinkowe i przechowują liczby całkowite dokładnie tylko do Number.MAX_SAFE_INTEGER, czyli 9 007 199 254 740 991. Dla większych liczb jest typ BigInt z literałami zakończonymi literą n.
function nwd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
const nwdRek = (a, b) => (b === 0 ? a : nwdRek(b, a % b));
const nww = (a, b) => (a / nwd(a, b)) * b;
console.log(nwd(252, 105), nwdRek(252, 105), nww(252, 105));
function nwdBig(a, b) {
while (b !== 0n) {
[a, b] = [b, a % b];
}
return a;
}
console.log(nwdBig(2n ** 70n, 6n ** 40n));
console.log(Number.MAX_SAFE_INTEGER);
Wynik w konsoli (Node.js 22.11.0):
21 21 1260
1099511627776n
9007199254740991
Liczba 2⁷⁰ jest większa niż Number.MAX_SAFE_INTEGER, więc wersja na zwykłych liczbach mogłaby zwrócić błędny wynik. nwdBig liczy dokładnie: NWD(2⁷⁰, 6⁴⁰) = 2⁴⁰ = 1 099 511 627 776.
Rozszerzony algorytm Euklidesa i odwrotność modulo
Rozszerzona wersja algorytmu oprócz NWD znajduje liczby całkowite x i y, dla których a · x + b · y = NWD(a, b). To tzw. współczynniki Bézouta. Dla 252 i 105 wychodzi x = −2 i y = 5, bo 252 · (−2) + 105 · 5 = 21.
def rozszerzony_euklides(a, b):
if b == 0:
return a, 1, 0
d, x, y = rozszerzony_euklides(b, a % b)
return d, y, x - (a // b) * y
d, x, y = rozszerzony_euklides(252, 105)
print(d, x, y)
print(252 * x + 105 * y)
print(pow(17, -1, 3120))
print(17 * 2753 % 3120)
Wynik w konsoli (Python 3.14.3):
21 -2 5
21
2753
1
Najważniejsze zastosowanie to odwrotność modulo, czyli liczba, która pomnożona przez daną daje resztę 1. W przykładzie 17 · 2753 daje resztę 1 przy dzieleniu przez 3120. W Pythonie od wersji 3.8 liczy ją wbudowane pow(a, -1, m), co opisuje dokumentacja. Na odwrotności modulo opiera się szyfrowanie RSA. W artykule, w którym Rivest, Shamir i Adleman opisali RSA, jeden wykładnik klucza liczy się z drugiego “odmianą algorytmu Euklidesa”.
NWD i metoda Euklidesa na maturze z informatyki
Ten algorytm jest wprost w podstawie programowej informatyki dla liceum i technikum. W zakresie rozszerzonym rozporządzenie wymienia “algorytm Euklidesa w wersji iteracyjnej i rekurencyjnej wraz z zastosowaniami”. W zakresie podstawowym uczeń stosuje algorytmy “działań na ułamkach z wykorzystaniem NWD i NWW”. Obie formuły pochodzą z rozporządzenia Ministra Edukacji z 28 czerwca 2024 roku (Dz.U. 2024 poz. 1019). Ten sam punkt podstawy obejmuje zamianę liczb między systemami liczbowymi.
Według informatora CKE informatykę zdaje się na maturze tylko na poziomie rozszerzonym, a egzamin sprawdza wymagania z tej podstawy. Trwa 210 minut, można zdobyć 50 punktów, a do około 60% z nich daje analiza algorytmów i programowanie. Jeśli zadanie każe go narysować, gotowy schemat jest w tekście o schematach blokowych. Szersze tło, od sortowania po struktury danych, daje przewodnik po algorytmach i strukturach danych.
Najczęstsze pytania o NWD i NWW
Czy NWD można policzyć dla liczb ujemnych i zera?
Wersja z resztą z dzielenia działa, jeśli najpierw weźmie się wartości bezwzględne. Tak robią funkcje wbudowane: math.gcd(-12, 18) i std::gcd(-12, 18) zwracają 6. NWD(a, 0) = |a|, a NWD(0, 0) według funkcji wbudowanych Pythona i C++ wynosi 0. Wersja z odejmowaniem wpada w pętlę bez końca, gdy dokładnie jedna z liczb wynosi zero.
Jak obliczyć NWD trzech liczb?
Liczy się je parami: NWD(a, b, c) = NWD(NWD(a, b), c). Euklides opisał to w twierdzeniu 3 księgi VII. W Pythonie od wersji 3.9 wystarczy math.gcd(252, 105, 84), które zwraca 21.
Czym różni się NWD od NWW?
NWD to największa liczba, która dzieli obie liczby. NWW to najmniejsza liczba, którą obie dzielą. Dla 252 i 105 NWD wynosi 21, a NWW 1260, i zawsze NWD · NWW = a · b dla liczb dodatnich.
Jak wygląda schemat blokowy algorytmu Euklidesa?
Ma jedną pętlę z warunkiem b ≠ 0, w środku obliczenie reszty i przesunięcie liczb, a na końcu wypisanie a. Gotowy schemat z kodem w Pythonie jest w naszym tekście o schematach blokowych, jako przykład 4.
Podsumowanie
Algorytm Euklidesa liczy NWD dwóch liczb na dwa sposoby. Wersja z odejmowaniem, opisana w księdze VII “Elementów”, odejmuje mniejszą liczbę od większej, aż się zrównają. Wersja z resztą z dzielenia zastępuje parę (a, b) parą (b, a mod b), aż reszta wyniesie zero. Wynik jest ten sam, ale wersja z resztą potrzebuje dużo mniej kroków: dla 252 i 105 trzy dzielenia zamiast pięciu odejmowań, a dla 1000 i 1 jedno zamiast 999. Najgorszy przypadek to kolejne liczby Fibonacciego, co udowodnił Lamé w 1844 roku. NWW liczy się wzorem a · b / NWD(a, b), dzieląc przed mnożeniem. W praktyce wystarczy math.gcd w Pythonie, od wersji 3.15 math.integer.gcd, albo std::gcd w C++17. JavaScript wymaga własnej funkcji, a dla dużych liczb typu BigInt.
Newsletter · DevstockAcademy & Kodożercy
Bądź na bieżąco ze światem IT, AI i automatyzacji
Co wtorek: newsy z branży, praktyczne tipy i narzędzia które warto znać. Zero spamu.
