Определение наибольшего делителя.

Наибольшим общим делителем (НОД) двух целых чисел m и n называется их общий делитель d (то естьd|m и d|n ), который делится на любой другой общий делитель m и n.

Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.

Наибольший общий делитель существует и однозначно определён (с точностью до знака) , если хотя бы одно из чисел m или n не ноль. Эффективным способом его вычисления является алгоритм Евклида.

тупо разложить на множители
Есть очень умные способы.

Простой - тупо делить на все простые числа от 2 до корня из N
еще тупее - на 2, потом на все нечетные до корня из N

Почему только до корня - сами сообразите

Вопрос не такой уж простой. Все упирается в то, не является ли число простым (т. е. существуют ли вообще делители кроме 1 и самого себя) . Доказать это не так-то просто (см. http://e-science.ru/math/theory/?t=2 ).

Вообще предлагается такой алгоритм: просто проверяем последовательно делимость числа N на простые числа, начиная с 2 и до sqrt(N). Частное от деления на наименьший простой делитель и будет наибольшим делителем N.

Начинаешь раскладывать число на простые сомножители и берешь наименьший. Теоретически может потребоваться пробовать числа вплоть до квадратного корня из числа, но можно ограничиться простыми числами. Затем делишь это число на найденный наименьший делитель, получаешь наибольший делитель.