Алгоритм Евклида

1. Вычислим r - остаток от деления числа a на b, a = bq+r, 0 <= r < b.

2. Если r = 0, то b есть искомое число.

3. Если r =/= 0, то заменим пару чисел (a,b) парой (b,r)
и перейдем к шагу 1.

// фукнция получения НОД
int NOD(int a, int b)
{
// пока числа не равны 0
while(a!=0 && b!=0)
{
if(a>=b) a=a%b;
else b=b%a;
}
return a+b; // Одно - ноль
}

При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

Читайте также:
  • Как перекодировать текст из 1251 в KOI-8R
    Вроде в МД есть какие-то функции (ну или по логике здравого смысла должны быть), а я всегда делал две строки типа char *strWIN="ABCDE...abcde...АБВГД...абвгд...123..[]{}..." и *strKOI="..." - то же самое, только в кодировке KOI, прочитанной под WIN. Потом ищешь номер буквы ко...
  • Преобразование чисел в строку и обратно
    В жизни программиста часто возникают ситуации, когда необходимо преобразовать int в char и обратно. Здесь хотел бы Вам показать несколько полезных примеров, оторыми пользуюсь сам.С/С++Include: stdlib.h или math.hФункции: double atof( char *string ); int atoi( char *str...
  • Расширенный алгоритм Евклида
    Алгоритм Евклида можно расширить так, что он не только даст НОД(a,b)=d, но и найдет целые числа x и y, такие что ax + by = d. Псевдокод.НА ВХОДЕ: два неотрицательных числа a и b: a>=bНА ВЫХОДЕ: d=НОД(a,b) и целые x,y: ax + by = d.1. Если b=0 положить d:=a, x:=1, y:=0 и возвратить (d,x,y)2. Полож...
  • Нахождение обратного элемента по модулю
    Для начала заметим, что элемент a кольца Zn обратим тогда и только тогда, когда НОД(a,n)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм. ПсевдокодНА ВХОДЕ: а из Zn.НА ВЫХОДЕ: обратный к а в кольце, если он существует.1. Использовать расширенный алгоритм Евк...
  • Решение линейных систем с трехдиагональной матрицей
    Первый из этих алгоритмов использует факторизацию системы, называется прогонкой или алгоритмом Томаса и входит во все классические учебники по численным методам. Второй алгоритм, также называемый алгоритмом редукции, использует последовательное бинарное исключение уравнений из системы; он менее из...