Рациональный множитель
(Время: 2 сек. Память: 16 Мб Сложность: 32%)
Дано натуральное число n. Разрешается умножать его на рациональное число p/q < 1, (p – простое число или единица, q – простое число), такое, что произведение опять натуральное. С получившимся в результате этого действия числом можно проделать такую же операцию (возможно, с другой дробью). Найти количество операций в одной из наиболее длинной последовательности таких действий.
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натуральное число n (1 ≤ n ≤ 106).
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно натуральное число – количество операций.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 2 | 1 |
| 2 | 3 | 2 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
