НОД (Наибольший общий делитель)

Английский эквивалент этого понятия GCD(Greatest Common Divisor). Краткую теорию по этому вопросу читаем на Wikipedia. Сразу отметим, что наиболее эффективный и распространенный алгоритм нахождения НОДа является алгоритм Евклида, о котором очень популярно изложено сайте MAXimal. Обратите внимание на доказательство корректности алгоритма.
После ознакомления с этой статьей предлагаю перейти к практической части.
По мотивам введения первой главы книги Левитина “Алгоритмы. Введение в разработку и анализ” рассмотрим несколько реализаций нахождения НОДа.
1. Рекурсивная реализация алгоритма Евклида:

1. int gcd_Euclid(int a, int b)
2. {
3.   if (b == 0)
4.     return a;
5.   return gcd_Euclid(b,a%b);
6. }

Есть аналогичная реализация этой функции, только вместо операции “остаток от деления” используется операция “вычитание”. Она представляет для нас чисто академический интерес, поэтому не будем ее разбирать отдельно. Достаточно понимать, что приведенная реализация работает быстрее.
2. Нерекурсивная реализация алгоритма Евклида:

1. int gcd_Euclid2(int a, int b)
2. {
3.   while (b!=0)
4.   {
5.     int tmp = a%b;
6.     a = b;
7.     b = tmp;
8.   }
9.   return a;
10. }

Любую рекурсивную функцию можно заменить на цикл while. Вопрос только каких усилий стоит поддерживать стек переменных. В данном случае это сделать несложно.
3. Первый алгоритм, который приходит в голову:

1. int gcd_Naive(int a,int b)
2. {
3.   int gcd = min(a,b);
4.   while (gcd != 1)
5.   {
6.     if (a%gcd == 0 & b%gcd == 0)
7.       return gcd;
8.     gcd--;
9.   }
10.   return gcd;
11. }

Как можно заметить данная реализация менее эффективна, по сравнению с предыдущими. Особенно это остро будет ощущаться если a = 1e9, b = 1.
4. Школьный метод разложения на простые множители:
Идея метода заключается в следующем. Раскладываем на простые множители числа а и b. Затем находим общие множители в обоих разложениях. Их произведение даст нужный ответ.

1. void findDivisors(int n,vector<int> &devs, vector<int> primes)
2. {
3.   // в массиве devs на i-ой позиции будет находится степень простого числа primes[i],
4.   // которое встречается в разложении числа n
5.   devs.resize(primes.size());
6.   for (int i = 0;i<primes.size();i++)
7.     while (n%primes[i]==0)
8.     {
9.       n/=primes[i];
10.       devs[i]++;
11.     }
12. }
13. int gcd_schoolMethod(int a, int b)
14. {
15.   // решето Эратосфена для чисел [2,1e4]
16.   const int size = 1e4;
17.   bitset<size> met;
18.   int len = sqrt((double)size);
19.   for (int i=2;i<=len;i++)
20.     for (int j=i*i;j<size;j+=i)
21.       met[j] = true;
22.   // копирование простых чисел в отдельный массив primes
23.   vector<int> primes;
24.   for (int i=2;i<size;i++)
25.     if (!met[i])
26.       primes.push_back(i);
27.  
28.   // поиск степеней простых чисел, встречающихся в разложении чисел a и b
29.   vector<int> divsA, divsB;
30.   findDivisors(a,divsA,primes);
31.   findDivisors(b,divsB,primes);
32.   int gcd = 1;
33.   for (int i=0;i<divsA.size();i++)
34.     gcd *= pow(primes[i],min(divsA[i],divsB[i]));
35.  
36.   return gcd;
37. }

В данной реализации условимся, что числа a и b находятся в интервале [1,10000].
1) Сначала находим все простые числа в интервале от [2,10000]
2) Затем формируем массив primes, который содержит только эти простые числа
3) Раскладываем числа a и b на простые множители. При этом получаем массивы divsA и divsB, в которых на i-ой позиции находится степень простого множителя, содержащегося в разложении. 
Разберем пример с числом 126.
126 = 2^1 * 3^2 * 5^0 * 7^1, где ^ – возведение в степень.
primes = {2,3,5,7,…}
divs   = {1,2,0,1,…}
4) Нахождение ответа осуществляется в цикле(33-34).

Очень удачно подмечено в сборнике лекций Михаила Густокашина, что имея разложение чисел в виде массивов степеней простых множителей, можно без труда сделать операцию сложения и вычитания первоначальных чисел.