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 × 3 × 5, a 75 to 3 × 5 × 5. Wspólne czynniki pierwsze to jedna 3 i jedna 5.

Pomnóż wspólne czynniki pierwsze: 3 × 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 × 5 i 3 × 5^2 dają 3 × 5.