1146. НОД

По заданному значению n вычислить значение G, где

Через НОД(i, j) обозначен наибольший общий делитель чисел i и j.

Для тех, кто не встречался со знаком суммирования объясняем, что значение G формально по приведённой формуле вычисляется при помощи следующего кода:

Здесь GCD() обозначает функцию нахождения наибольшего общего делителя двух чисел.

Вход. Состоит не более чем из 100 строк. Каждая строка содержит единственное натуральное число n (1 < n < 501). Последняя строка содержит n = 0 и не обрабатывается.

Выход. Для каждого входного значения n вывести в отдельной строке соответствующее значение G.

Пример входа	Пример выхода
10 100 500 0	67 13015 442011

РЕШЕНИЕ

теория чисел

Анализ алгоритма

Поскольку n < 501, то задачу можно решить при помощи двойного цикла, выполнив вычисления по приведенной формуле.

Реализация алгоритма

Функция gcd находит наибольший общий делитель.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b,a % b);

}

Основная часть программы. Читаем входное значение n, вычисляем и выводим значение суммы g.

while(scanf("%d",&n), n)

{

g = 0;

for(i = 1; i < n; i++)

for(j = i + 1; j <= n; j++)

g += gcd(i,j);

printf("%d\n",g);

}