Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1716. Головоломка
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 17/03/2012 | Южно-Уральский открытый командный чемпионат по программированию (E) |
| 24/03/2012 | Занятие 12 (E) |
| 04/07/2022 | Лето 2022-4 (A) |
Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Стартовав с числа 1, нужно получить некоторое заданное число `N`.
На каждом шаге можно добавлять к текущему числу один из его делителей, чтобы получить новое число.
Например, для первого шага у нас только один вариант: добавить 1 к 1 и получить 2.
На втором шаге можно выбрать один из двух делителей и получить число 2+1=3 или 2+2=4. От
числа 4 на третьем шаге можно перейти к числам 5, 6 или 8 в зависимости от выбранного делителя.
Напишите программу, определяющую минимальное количество шагов для получения заданного числа `N`.
Формат ввода
Ввод содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 10^5`).
Формат вывода
Вывести одно целое число – минимальное количество шагов.
Пример ввода
6
Пример вывода
3
