Rešenje grubom silom podrazumeva da se broj \(p\) na sve moguće načine razloži na proizvod \(p = a \cdot b\) i da se izračuna NZD za sve tako dobijene parove. Bez gubitka na opštosti se može pretpostaviti da je \(a \leq b\), pa se zato pronalaze svi delioci \(a \leq \sqrt{p}\). NZD dva broja se može izračunati Euklidovim algoritmom.
Pronalaženje delilaca vršimo u složenosti \(O(\sqrt{p})\), a računanje njihovog NZD-a u složenosti \(O(\log{p})\). Stoga ukupnu služenost možemo oceniti sa \(O(\sqrt{p}\log{p})\).
Rastavimo \(p\) na proste činioce, tj. pretpostavimo da je \(p = p_1^{\alpha_1}\ldots p_k^{\alpha_k}\).
Dva činioca \(a\) i \(b\) treba odrediti tako da im je NZD što veći, tj. da imaju što više zajedničkih prostih faktora. Stoga je najbolje da prvi broj bude jednak
\[a = p_1^{\left\lfloor{\frac{\alpha_1}{2}}\right\rfloor}\ldots p_k^{\left\lfloor{\frac{\alpha_k}{2}}\right\rfloor}\]
a drugi broj bude jednak \(b = \frac{p}{a}\). Broj \(b\) je deljiv brojem \(a\) i NZD ta dva broja jednak je \(a\). To je ujedno najveći NZD koji se može dobiti.
Složenost potiče od složenosti faktorizacije i iznosi \(O(\sqrt{p})\). Pošto se broj deli svojim faktorima, algoritam se često izvršava samo do korena najvećeg prostog faktora broja \(p\), što može značajno uticati na vreme izvršavanja u takvim primerima.