3259. Делители

Найдите наименьшее натуральное число x, имеющее ровно n делителей.

Вход. Одно натуральное число n (1 ≤ n ≤ 16).

Выход. Выведите наименьшее натуральное число x, у которого ровно n делителей.

Пример входа 1	Пример выхода 1
2	2
Пример входа 2	Пример выхода 2
4	6

РЕШЕНИЕ

теория чисел - делители

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

Перебираем натуральные числа x = 1, 2, 3, … . Для каждого x считаем количество его делителей. Как только найдено число, у которого количество делителей равно n, выводим его и завершаем работу.

Такое решение укладывается в ограничение по времени, так как значение n не велико. Например, для n = 16 ответ равен 120.

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

Функция Divisors подсчитывает количество делителей числа n с помощью простого перебора всех возможных делителей от 1 до n.

int Divisors(int n)

{

int res = 0, i;

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

if (n % i == 0) res++;

return res;

}

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

scanf("%d",&n);

Последовательно перебираем натуральные числа i = 1, 2, 3, … и для каждого из них вычисляем количество делителей. Как только находится число i, у которого ровно n делителей, цикл прекращается.

for (i = 1; ; i++)

{

d = Divisors(i);

if (d == n) break;

}

Выводим ответ.

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