Nejjednodušším způsobem výpočtu největšího společného dělitele je rozložit jednotlivá zkoumaná čísla na prvočísla a z nich vybrat prvočinitele v maximální společné mocnině. Vynásobením prvočinitelů v příslušných mocninách získáme největšího společného dělitele daných čísel.

Rozklad na prvočísla (faktorizace) je z výpočetního hlediska velmi náročný problém. Proto pro efektivní výpočet největšího společného dělitele velkých čísel používáme Euklidův algoritmus.

Vstupem algoritmu jsou dvě přirozená čísla a . Algoritmus v každém svém kroku vydělí se zbytkem číslo číslem . Pokud zbytek není nulový, tak do přiřadí číslo a zbytek po dělení přiřadí do uvolněné proměnné a celý postup opakuje.