Программирование различных типов задач
... простых чисел остается таким же четким и ясным сегодня, каким оно было более двух тысяч лет...
А значит НОД(a,b) = НОД(a-b, b). Применяя эту формулу a div b раз, получим требуемое. Для нахождения НОД можно использовать следующий алгоритм Евклида