3259. Делители

Найдите наименьшее возможное натуральное число x, у которого ровно n делителей.

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

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

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

РЕШЕНИЕ

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

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

Перебираем числа x = 1, 2, 3, … и выводим первое, которое содержит в точности n делителей. Такое решение пройдет по времени, так как n не велико.

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

Функция Divisors подсчитывает количество делителей в числе 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);