Największy wspólny dzielnik dwóch liczb, liczony szybko metodą Euklidesa. Z animacją.
NWD to największa liczba, przez którą dzielą się bez reszty obie dane liczby. Na przykład NWD liczb 12 i 18 to 6, bo 6 dzieli i 12, i 18, a nic większego już nie.
Jak to policzyć szybko? Zamiast sprawdzać po kolei wszystkie dzielniki, używamy sztuczki Euklidesa. Zauważył on, że NWD dwóch liczb nie zmienia się, gdy większą liczbę zastąpimy resztą z jej dzielenia przez mniejszą. Powtarzamy to, aż jedna z liczb stanie się zerem – wtedy druga liczba jest szukanym NWD.
Przykład dla 48 i 36: 48 mod 36 = 12, więc para robi się (36, 12). Dalej 36 mod 12 = 0, więc para to (12, 0). Zostało zero, więc NWD to 12.
Na maturze: NWD przydaje się przy skracaniu ułamków oraz jako krok do policzenia NWW. Wersja Euklidesa jest tak krótka, że warto ją znać na pamięć.
Zobacz metodę Euklidesa krok po kroku. W każdym kroku większą liczbę zastępujemy resztą z dzielenia (a mod b), aż jedna z liczb spadnie do zera. Wtedy druga liczba to szukany NWD.
Naciśnij „Krok", aby wykonać jedno dzielenie z resztą, albo „Auto".
funkcja nwd(a, b): dopóki b ≠ 0: r ← a mod b // reszta z dzielenia a ← b b ← r zwróć a
def nwd(a, b):
"""Zwraca największy wspólny dzielnik a i b (metoda Euklidesa)."""
while b != 0:
a, b = b, a % b # większą liczbę zastępujemy resztą
return a
# Przyklady uzycia
print(nwd(48, 36)) # Wynik: 12
print(nwd(17, 5)) # Wynik: 1#include <iostream>
using namespace std;
int nwd(int a, int b) {
while (b != 0) {
int r = a % b; // reszta z dzielenia
a = b;
b = r;
}
return a;
}
int main() {
cout << nwd(48, 36) << endl; // Wynik: 12
cout << nwd(17, 5) << endl; // Wynik: 1
}Największy Wspólny Dzielnik – największa liczba, przez którą dzielą się bez reszty obie dane liczby.
Bo zamiast przeglądać wszystkie liczby po kolei, w każdym kroku mocno zmniejsza liczby (biorąc resztę). Dochodzi do wyniku w kilku krokach nawet dla ogromnych liczb.
Gdy liczby nie mają żadnego wspólnego dzielnika poza jedynką. Mówimy wtedy, że są względnie pierwsze – na przykład 17 i 5.
Przy skracaniu ułamków do najprostszej postaci i przy liczeniu najmniejszej wspólnej wielokrotności (NWW).
Policz NWD i wpisz wynik, potem kliknij Sprawdź.
NWD liczb 12 i 18 to . NWD liczb 100 i 40 to . NWD liczb 7 i 13 to .
Uzupełnij kolejne kroki Euklidesa dla 48 i 36:
| Para (a, b) | a mod b |
|---|---|
| (48, 36) | |
| (36, 12) |
Zostało zero, więc NWD to .
O(log min(a,b))O(1)Metoda Euklidesa jest bardzo szybka – liczba kroków rośnie tak wolno jak log z mniejszej liczby, czyli O(log min(a,b)). Pamięci używa tyle co nic (O(1)), bo wystarczą dwie zmienne.
Te zadania CKE sprawdzają dokładnie to zagadnienie – link prowadzi wprost do treści podpunktu w arkuszu:
Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: