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

Для заданного натурального числа n выведите его наибольший делитель, отличный от 1.

Вход. Одно натуральное число n (1 < n < 2³¹).

Выход. Выведите наибольший делитель числа n, отличный от n.

Пример входа 1	Пример выхода 1
21	7
Пример входа 2	Пример выхода 2
97	1

РЕШЕНИЕ

делители

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

Переберем делители числа n от 2 до и найдем минимальный. Если i (2 ≤ i ≤ ) – наименьший делитель n, то n / i будет наибольшим делителем n, отличным от n.

Если делителей в интервале [2; ] не оказалось, то ответом будет число 1.

Пример

Если n = 21, то его наибольшим делителем будет 7.

Если n = 13 (простое число), то его наибольшим делителем будет 1.

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

Читаем входное значение n.

scanf("%d", &n);

Установим flag = 0. Перебираем возможные делители от 2 до . При нахождении первого же (наименьшего) делителя устанавливаем flag = 1, выводим делитель и выходим из цикла.

for (i = 2; i <= sqrt(n); i++)

if (n % i == 0) break;

Если делитель был найден на прмежутке [2; ], то выводим n / i.

if (i <= sqrt(n)) printf("%d\n", n / i);

Если делитель не был найден, то число n простое. Выводим 1.

else printf("1\n");