Załóżmy, że chcemy wyznaczać największy wspólny dzielnik dla wielu par stosunkowo niewielkich liczb. A konkretnie – dla  par liczb całkowitych dodatnich nieprzekraczających  Stosując algorytm Euklidesa, otrzymujemy oczywiście algorytm o złożoności czasowej  Możemy także spamiętać w dużej tablicy odpowiedzi na wszystkie możliwe  zapytań. Wówczas przy pierwszym podejściu możemy otrzymać złożoność  gdy dla każdej możliwej pary zastosujemy niezależnie algorytm Euklidesa. Bez problemów takie rozwiązanie możemy przyspieszyć do  ponieważ pojedynczy krok algorytmu Euklidesa sprowadza wyznaczanie NWD dla pary  do problemu obliczenia NWD dla pewnej pary leksykograficznie mniejszej. Możemy zatem wypełniać tablicę w odpowiedniej kolejności i w każdym kroku przepisywać wynik ze wskazanej komórki. W praktyce lepiej w tej sytuacji korzystać z algorytmu Euklidesa w wersji z odejmowaniem, gdyż procesory wykonują je istotnie szybciej niż wyznaczanie reszty z dzielenia. Otrzymujemy w ten sposób następujący algorytm:

Czas obliczeń wstępnych rzędu  jest jednak mało satysfakcjonujący – dopiero przy  zapytaniach podejście korzystające z algorytmu Euklidesa przestaje osiągać lepsze wyniki.

Spróbujmy odnieść pewne korzyści już z obliczeń wstępnych rzędu  Jak przekonaliśmy się w poprzednim artykule, w tym czasie można wyznaczyć wszystkie liczby pierwsze nieprzekraczające  Zaprezentowany tam algorytm jest jednak znacznie silniejszy – dla każdej liczby  oblicza jej najmniejszy dzielnik pierwszy (oznaczany tu przez ) oraz największą potęgę tego  dzielącą  Za ich pomocą można łatwo skonstruować algorytm znajdowania NWD, działający w czasie proporcjonalnym do liczby różnych dzielników pierwszych argumentów. Pesymistycznie wielkość ta wynosi  więc zapytania obsługiwane są niewiele szybciej niż przez algorytm Euklidesa. Okazuje się jednak, że przy liniowych obliczeniach wstępnych można osiągnąć stały czas zapytania!

Na wstępie zauważmy, że jeśli jeden z argumentów jest liczbą pierwszą, obliczenie NWD jest bardzo łatwe. Również łatwo możemy wyznaczać NWD liczb mniejszych niż : jeśli mamy do dyspozycji czas  na obliczenia wstępne, można spamiętać wszystkie wartości NWD, wywołując  Jak się wkrótce przekonamy, dowolne zapytanie o NWD można sprowadzić do stałej liczby zapytań, w których każdy z argumentów jest liczbą pierwszą lub nie przekracza  Kluczowe jest tu pojęcie rozkładu specjalnego.

Przykładowo, jednym z rozkładów specjalnych liczby  jest  liczby  jest  a liczby  jest

Następujący lemat stanowi podstawę indukcyjnego dowodu faktu, że każda dodatnia liczba całkowita ma rozkład specjalny. Ten dowód można natychmiast przekształcić w algorytm wyznaczający rozkłady specjalne wszystkich liczb od  do  w czasie liniowym na podstawie tablicy

Pozostaje nam jeszcze wykorzystać rozkłady specjalne do efektywnego obliczania NWD. Tym razem najpierw przedstawimy algorytm, a potem zastanowimy się nad jego poprawnością. Przyjmiemy, że rozkłady specjalne zapamiętaliśmy w tablicy

Na początek zauważmy, że w każdym obrocie pętli  jest pewnym wspólnym dzielnikiem  oraz  Co więcej,  jest największym wspólnym dzielnikiem  oraz  Jeśli  lub  nie mamy co do tego wątpliwości. Bez straty ogólności niech więc  oraz  Wówczas  jest liczbą pierwszą, a więc  może być równe  lub  Drugą możliwość natychmiast wyklucza nierówność

Pozostaje teraz wykazać, że  Zrobimy to przez wskazanie niezmienników pętli:

• 
• 
•  dla już przetworzonych par

Na ich podstawie wnioskujemy, że po ostatnim obrocie pętli  jest wspólnym dzielnikiem  i   a liczby  i   są względnie pierwsze.

W ten sposób skonstruowaliśmy algorytm, który na  zapytań o NWD liczb z zakresu  odpowiada w czasie  O ile tylko  to ten algorytm jest najlepszy z tutaj przedstawionych. Okazuje się, że w pewien sposób można połączyć jego siły z algorytmem Euklidesa i otrzymać rozwiązanie, które nigdy nie jest asymptotycznie wolniejsze od żadnego z zaprezentowanych, a dla pewnych wartości (np. ) jest niemal  razy szybsze. Stworzenie tego działającego w czasie  algorytmu pozostawiamy Czytelnikowi jako zadanie.