Наибольший общий делитель

Два числа называются взаимно простыми,если у них нет общих множителей кроме 1. Иными словами, е с-ли наибольший общий делительа и п равен 1. Это записывается как:

НОД(а,и)=1

Взаимно просты числа 15 и 28. 15 и 27 не являются взаимно простыми, а 13 и 500 - являются. Простое число взаимно просто со всеми другими числами, кроме ч исел, кратных данному простому числу.

Одним из способов вычислить наибольший общий делитель двух чисел является алгоритм Эвклида.Эвк-лид описал этот алгоритм в своей книге, Элементы, написанной в 300 году до нашей эры. Он не изобрел его. Историки считают, что этот алгоритм лет на 200 старше. Это самый древний нетривиальный алгоритм, который дошел до наших дней, и он все еще хорош. Кнут описал алгоритм и его современные модификации в [863]. На языке С:

/* возвращает НОД (gcd) x и у */ int gcd (int x, int у) {

int g;

if (x < 0)

x = -x;

if (У < 0)

у = ~y;

if (x + у == 0 ) ERROR ;

g = у;

while (x > 0) {

g = x;

x = у % x;

у = g; }

return g; }

Этот алгоритм можно обобщить для получения НОД массива т чисел:

/* возвращает НОД (gcd) xl, x2...xm */ int multiple_gcd (int m, int *x) { slze_t i; int g; if (m < 1)

return 0; g = x [0]; for (i=l; i<m; ++i) {

g = gcd(g, x[i]); /* оптимизация, так как для случайных x[i], g==l в 60% случаев: */ if (g == 1) return 1; }

return g; }