NWD z rozkładu na czynniki pierwsze

Wypisywanie dzielników staje się powolne przy większych liczbach, a rozkład na czynniki pierwsze jest szybszy. Rozłóż obie liczby na czynniki: 45 to $3\cdot 3\cdot 5$, a 75 to $3\cdot 5\cdot 5$. Wspólne czynniki pierwsze to jedna 3 i jedna 5.

Pomnóż wspólne czynniki pierwsze: $3\cdot 5$ to 15, czyli NWD liczb 45 i 75. Czynnik pierwszy liczy się jako wspólny tylko tyle razy, ile występuje w obu liczbach: 45 ma dwie trójki, ale 75 ma tylko jedną, więc uwzględniamy tylko jedną 3.

Dlaczego to działa: wspólny czynnik może być zbudowany tylko z liczb pierwszych występujących w obu liczbach. Wzięcie każdego wspólnego czynnika pierwszego tyle razy, na ile pozwalają obie liczby, daje największy taki czynnik. W przypadku wykładników weź każdy wspólny czynnik pierwszy z mniejszym wykładnikiem: ${3}^{2}\cdot 5$ i $3\cdot {5}^{2}$ dają $3\cdot 5$.